MastersForum

Erkläre mir mal den Sinn, ich lausche gespannt....

worf is sicher am fussballschauen, aber das kann ich dir auch erklären:

damit ist gemeint, dass es sinnlos ist, jemanden etwas zu erklären, der es ohnehin nicht verstehen will (oder kann)

Toddi, der jetzt auch filmschauen geht.

Danke das Du ihm hilfst, nur das seine Ergüsse nicht wertvoll sind und somit dieses Sprichwort nicht passt.

Du bist so unglaublich dum Dude, das löst bei mir echt nen Brechreiz aus. Und deine bescheuerte "Imme noch arbeitslos?" Antwort kannst du dir auch sparen.

dude geh doch einfach deinen wertvollen verwaltungsjob machen und beschäftige dich mit den ernsten problemen des alltags anstatt deine kapazitäten an so total unwichtige dinge wie theoretische wissenschaften zu vergeuden; die ganzen nerd kasperles haben eh keinen bezug zur realität und beten nur den wertlosen unikrams runter, gibt schliesslich auch überhaupt keine indizien, dass mathematik überhaupt relevant ist, bis auf vielleicht so kleine zufälle in der physik wie die quantentheorie, auf der ja nur sämtliche moderne geräte basieren.

Zitat

Original von GEC|Napo
Du bist so unglaublich dum Dude, das löst bei mir echt nen Brechreiz aus. Und deine bescheuerte "Imme noch arbeitslos?" Antwort kannst du dir auch sparen.

Siehst Du Worf so beleidigt man ehrlich und richtig.

Napo das Wörtchen arbeitslos macht Dir aber zu schaffen, ist doch nicht schlimm wenn dem so wäre oder?
@Nague Mathe ist schon wichtig, ich fasse es mal so zusammen. Die Mathematik braucht keinen Worf aber ein Worf braucht die Mathematik.

P = Programme die einfach nur den Quelltext abarbeiten
(Beispiel Sortierungsprogramm)

NP = Kompolexere Programme die sich verändern können durch Zufallszahlen oder ähnliches. (Beispiel Minesweeper,Sudoku)


Und jetzt wollen die Leute wissen ob man/eine Maschine diese Programme auch mit dem selben Algorithmus lösen kann?
Würd mich freuen wenns einer kurz erklärt der Ahnung hat. Falls man das Grundproblem überhaupt schnell erklären kann.

Und bitte kein Satz ala
"Das P=NP-Problem ist ein offenes Problem der theoretischen Informatik speziell der Komplexitätstheorie . Es ist die Frage ob die Klasse NP mit der von deterministischen Turingmaschinen in Polynomialzeit entscheidbaren Problemen (der Klasse P ) übereinstimmt. "

Zitat

Original von Invader
P = Programme die einfach nur den Quelltext abarbeiten
(Beispiel Sortierungsprogramm)

NP = Kompolexere Programme die sich verändern können durch Zufallszahlen oder ähnliches. (Beispiel Minesweeper,Sudoku)

Das stimmt so nicht. Die Klassen P und NP beziehen nicht nur auf Probleme, nicht auf deren Lösungen (=Programme).

Ganz populärwissenschaftlich kann man es so ausdrücken:
In P sind alle Probleme drin, für deren Lösung definitiv eine Algorithmus existiert, der in polynomieller Zeit arbeitet.

In NP sind all die Probleme drin, bei denen man die Korrektheit der bzw. einer (zufällig geratenen) Lösung in polynomieller Zeit zeigen kann.
Beispiel: Hamiltonkreis

Ist der Unterschied klar? Beide Klassen benötigen genauso "viel" Zeit. Aber bei Problemen in P fordert man, dass man die Lösung aus allen möglichen Varianten findet, bei denen in NP fordert man "nur", dass man eine korrekte Lösung (wenn man sie denn zufällig geraten hat) als solche erkennt.
Die Vermutung ist nun, dass zu der zweiten Klasse mehr Probleme gehören als zur ersten Klasse.

Und das ist wiederum praktisch wichtig für z.B. Verschlüsselungstechniken. Diese basieren ja darauf, dass es extrem schwer ist, die korrekte Lösung zu finden, es aber sehr einfach ist, eine korrekte Lösung zu überprüfen.

Danke für die Hilfestellung!


Für mich ist der Unterschied jetzt das man alle P Probleme mit dem richtigen Algorithmus optimal lösen kann.

Bei NP Problemen hingegen geht man davon aus das eine perfekte Lösung nicht möglich ist und versucht sich der Lösung so nah wie möglich anzunähern, so das sie offensichtlich nicht falsch ist.

Was passiert nun wenn man zu einem NP Problem einen Algorithmus findet der das Problem sicher korrekt löst? Wird es automatisch zu einem P Problem?


Irgendwie habe ich das Gefühl das ichs noch nicht 100% verstanden habe.

P ist die Menge aller Sprachen, die von einer deterministischen Turingmaschine in einer von einem Polynom begrenzten Anzahl Schritten entschieden werden kann.

NP ist die Menge aller Sprachen, die von einer nichtdeterministischen Turingmaschine in einer von einem Polynom begrenzten Anzahl Schritten entschieden werden kann.

Deterministische Turingmaschinen sind daher so ziemlich die Abstraktion von Programmiersprachen (man möchte Beweise etc. immer allgemeingültig machen und sich mit "einfachen" Dingen beschäftigen, daher benutzt man Turingmaschinen).

Wenn ein Problem nachweislich in P liegt, dann kann man ein Programm schreiben, das das Problem in einer Laufzeit löst, die von einem Polynom beschränkt ist. Man sucht immer nach solchen Algorithmen, die von (möglichst kleinen) Polynomen beschränkt sind, da Algorithmen ohne solche Schranken (zB einfach alles ausprobieren => exponentielle Laufzeit) sehr schnell exorbitant hohe Laufzeiten aufweisen.

Nun gibt es Algorithmen, zu denen man keine polynomiellen Algorithmen hat und manche davon liegen eben in NP. So eine nichtdeterministische Turingmaschine ist ein schlecht greifbares Konstrukt, aber die Probleme in NP haben alle die Eigenschaft, dass man in polynomieller Zeit überprüfen kann, ob eine Lösung korrekt ist.

Wenn man nun P=NP zeigt, dann weiß man, dass es polynomielle Algorithmen für alle Probleme in NP geben muss. Insbesondere gibt es sogenannte NP-vollständige Probleme: Wenn man solch ein Problem in polynomieller Laufzeit lösen könnte, dann könnte man sie alle in polynomieller Laufzeit lösen, da sich alle NP-Probleme auf NP-vollständige Probleme (polynomiell) reduzieren lassen. Deshalb würde es reichen, wenn man ein NP-vollständiges Problem in polynomieller Zeit lösen könnte. Daraus würde P=NP folgen.

Nun konnte man allerdings für keines der NP-vollständigen Probleme bisher einen polynomiellen Algorithmus finden. Das wirft die Frage auf, ob es solche überhaupt gibt. Zeigt man, dass P != NP, dann heißt das automatisch, dass es überhaupt nicht möglich ist, polynomielle Algorithmen für die NP-vollständigen Probleme zu finden. Dann braucht man da auch keine Zeit investieren, sondern muss sich etwas anderes ausdenken (zB Näherungslösungen).

Es ist so ein bisschen die Sache, dass es eben Probleme gibt, zu denen man bis jetzt keine vernünftigen Lösungen gefunden hat (zB Traveling-Salesman-Problem). Die P=NP? Fragestellung ist so ein bisschen die Frage, ob der Grund dafür ist, dass man
a) bisher zu dumm war.
b) es solche vernünftigen Lösungen einfach nicht gibt.

Zitat

Und bitte kein Satz ala "Das P=NP-Problem ist ein offenes Problem der theoretischen Informatik speziell der Komplexitätstheorie . Es ist die Frage ob die Klasse NP mit der von deterministischen Turingmaschinen in Polynomialzeit entscheidbaren Problemen (der Klasse P ) übereinstimmt. "

Zitat

P ist die Menge aller Sprachen, die von einer deterministischen Turingmaschine in einer von einem Polynom begrenzten Anzahl Schritten entschieden werden kann. NP ist die Menge aller Sprachen, die von einer nichtdeterministischen Turingmaschine in einer von einem Polynom begrenzten Anzahl Schritten entschieden werden kann.

fail

Ich habe die "Definition" hingeschrieben, aber versucht, unten zu erklären, worum es so halbwegs geht.

Hinzufügen sollte man übrigens noch, dass man polynomiell immer von den Eingabegrößen abhängig macht (wenn man es von nichts abhängig macht, macht es keinen Sinn).

Ich finde die Erklärung von plizzz ziemlich gut.

du bist auch informatiker. ich hab nach wie vor nix verstanden

find die erklärung von plizz auch gut verständlich und ich bin kein informatiker

danke.

Tjo Marinero und Plizz schreiben es so das man sogar als Fachfremder was versteht und sogar neugierig wird....

...,nicht so wie...

Zitat

Original von jens
find die erklärung von plizz auch gut verständlich und ich bin kein informatiker

danke.

same

Ich merke, dass ich aus der "Angwandten Informatik"-Ecke komme, ich habe zwar einen groben Überblick über das Thema, aber keine tiefgreifende Kenntnisse (würde mir bei meiner tatsächlichen Arbeit auch nicht helfen, ist aber trotzdem interressant).

Ich frage mich gerade, ob es Probleme gibt, die auch mit der nicht-deterministischen Turingmaschine nicht berechnet werden können.

Also Probleme, deren Lösung man nicht kennt (aber weiss das sie existiert) und das überprüfen der Lösung selbst auch NP-Komplexität hat.

Zitat

Original von MaxPower
Ich merke, dass ich aus der "Angwandten Informatik"-Ecke komme, ich habe zwar einen groben Überblick über das Thema, aber keine tiefgreifende Kenntnisse (würde mir bei meiner tatsächlichen Arbeit auch nicht helfen, ist aber trotzdem interressant).

Ich frage mich gerade, ob es Probleme gibt, die auch mit der nicht-deterministischen Turingmaschine nicht berechnet werden können.

Also Probleme, deren Lösung man nicht kennt (aber weiss das sie existiert) und das überprüfen der Lösung selbst auch NP-Komplexität hat.

Es gibt sowohl Probleme die prinzipiell nicht berechenbar sind (z.B. Halteproblem) als auch Probleme die berechenbar sind, aber nicht in NP liegen. Wobei ich bei letzteren jetzt ohne nachzusehen nicht sicher bin, ob das tatsächlich gezeigt oder bisher nur vermutet wurde (also nur noch nicht gezeigt werden konnte, dass sie in NP liegen). Viele von Brettspielen (Schach, Go, etc.) inspirierte Probleme fallen darunter.

Okay, hab mal kurz gegoogelt: Erreichbarkeit in Petrinetzen ist EXSPACE-schwer und daher nicht in NP, weil NP eine echte Teilmenge von EXSPACE ist.
Noch ein zweites aus wikipedia:
An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions are limited to four operators: union, concatenation, the Kleene star (zero or more copies of an expression), and squaring (two copies of an expression).