Diskussion:P-NP-Problem/Archiv/1

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:P-NP-Problem/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:P-NP-Problem/Archiv/1#Thema_1

Überarbeiten

Irgendwie stellt mich der Artikelname noch nicht zufrieden. Sollte es nicht P-NP-Problem heißen? Stern 23:33, 25. Mai 2004 (CEST)

naja, eigentlich müsste es wohl P \stackrel{?}{=} NP (d.h. ein = mit einem Fragezeichen drüber) heißen, aber das ist doch wohl kein brauchbarer Artikelname... Aber nur diese Formulierung drückt das eigentliche Problem aus. --Pinguin.tk 23:58, 25. Mai 2004 (CEST)

Ich finde, der Artikel bedarf einer Überarbeitung, da es das größte ungelöste Problem der theoretischen Informatik ist. Das verdient einen starken, allgemeinverständlichen und ausführlichen Artikel, etwa wie in der englischen Wikipedia vorzufinden [1]. Ylloh 22:35, 18. Dez. 2006 (CET)

Ich finde auch ,dass es mal ordentlich(!) überarbeitet werden muss.Und dabei sollte man am Namen des Artikels Anfangen . Ich bin für P versus NP

Nach P-NP-Problem verschoben und Einleitung überarbeitet--Spid 17:45, 15. Mär. 2007 (CET)

Die Einleitung ist noch verbesserungsbedürftig:

Es stellt die Frage, ob Probleme existieren, für die eine gegebene Lösung leicht überprüft werden kann, das Finden einer solchen Lösung jedoch extrem schwierig ist.

Wieso "leicht überprüft werden kann"? Gemäßt Definition von NP immerhin nur nichtdeterministisch! Wieso "extrem schwierig"? Gemeint ist, dass die Berechnung dieser Probleme mehr als polynomiellen Zeitaufwand erfordert. Lösungsverfahren sind in der Regel bekannt, jedoch ist offen, ob es auch mit nur polynomiellem Zeitaufwand geht. --Bri B. 11:55, 15. Feb. 2010 (CET)

Lösungsversuche

Vllt sollte man erwähnen ,dass es schon in der Vergangenheit versuche gab ,das Problem zu lösen : man siehe : Mikhail Kupchik: http://users.i.com.ua/~zkup/pvsnp_en.pdf oder Anatoly D. Plotnikov : http://www.heise.de/newsticker/meldung/12512

Es gibt jedoch viele Anzeichen dafür, dass tatsächlich gilt: P≠NP. Könnte man diese Anzeichen auch beim Namen nennen, nur um es nachprüfbar zu machen? --Bolliver 00:26, 5. Feb 2005 (CET)

Der Artikel ist sehr technisch. Ich finde man sollte versuchen auch Leute die nicht auf diesem Gebiet bewandert sind eine Chance zu geben die Problematik wenigstens annähernd zu verstehen. Eine sehr schöne und völlig von Fachbegriffen freie Erklärung dr Problematik habe ich auf der Seite des Clay-Preises gefunden: http://www.claymath.org/millennium/P_vs_NP/ Natürlich sollte der Rest auch bleiben...

Der Artikel ist eher theoretisch als technisch. Habe mir erlaubt ein wenig Alltagsnähe einzufügen. --84.174.222.145 18:42, 11. Okt 2005 (CEST)

"Ein alltägliches Problem ist das ausschneiden von Formen aus einem Kuchenteig" Müsste es nicht korrekterweise "beliebige Formen" heissen. Das Rucksack Problem geht doch davon aus, wenn ich mich nicht irre. Für bestimmte Formen gibt es doch zum Bsp. Lösungen aus der Algorithmischen Zahlentheorie. --80.129.139.50 02:07, 12. Okt 2005 (CEST)

Hmm.. Hat mein Info-Tutor gmeint. Aber sicher hast du recht, dass es um eine etwas andere Form des Rucksackproblems geht und "verschiedenen" sollte da schon stehen. Dann gibt es halt den Tradeoff zwischen "Wertigkeit" der Komponenten und Materialverbrauch. Es ist auch die Frage ob die mathmatische Lösung nicht eine elends hohe Laufzeit hat, kennt jemand eine solche? --84.174.140.160 08:12, 13. Okt 2005 (CEST)

Sagtmal, von euch hat nicht zufällig irgendjemand ne klitzekleine Idee für die Lösung? Unser Theo-Info-Prof meinte, jemand der ihm die Lösung zu diesem Problem präsentiert würde den Schein ohne Klausur bekommen. Und das erscheint mir derzeit als einfacher :D *scnr* --Patrick H 15:23, 31. Jan 2006 (CET)

Wie wärs damit: Differenzieren ist Handwerk, Integrieren ist Kunst, und Differentialgleichungen sind Glückssache. Schreib einfach eine Funktion auf, die leicht diff-bar aber schwer int-bar ist, ergo N <> NP und schwuppdiwupp, hast du deinen Schein. Zum Beispiel exp(-1/x) könnte so eine Funktion sein, weil sie ganz schlecht (am Punkt Null) in eine Taylorreihe zu expandieren geht.

Als nicht-Informatiker bzw nicht-Mathematiker hätte ich dazu eine kurze Frage, vorrausgesetzt jemand möge sie mir beantworten ;) Wie darf ich denn eine 'nicht-deterministische Turingmaschine' mir vorstellen, bzw den Unterschied einer 'deterministischen' und einer 'nicht-deterministischen'? Wäre nett wenn da jemand mir kurz weiterhelfen würde. Vielen Dank. :) --Cardiba 12:49, 18. Feb 2006 (CET)

@ Patrik: wenn ich die wüsste würde ich sie dir bestimmt nicht sagen sondern die 1 Mille € selber einkassieren @ Cardiba: Deterministisch = Vorherbestimmt Nichtdeterm. = Zufällig... @ beide: eigentlich gehört sowas nicht hierher, aber naja K. Ernst 20:08, 8. Apr 2006 (CEST)

Den Link auf den humoristischen Beweis würde ich persönlich entfernen. Er ist weder besonders lustig, noch relevant. Was meint ihr?

Hi! Weiß jmd. von euch, ob die Teufelstreppe eine Falltür ist?

PUBLIC-KEY

"Auf der (momentan) praktischen Unlösbarkeit von NP-Lösungsalgorithmen baut unter anderem das Public-Key-Verfahren auf."

Ist das so??? Ich glaube nicht.--88.64.146.65 03:12, 31. Jan. 2007 (CET)

Warum denn nicht?

http://de.wikipedia.org/wiki/RSA-Kryptosystem#Einwegfunktionen

http://de.wikipedia.org/wiki/Einwegfunktion

Zahnradzacken

Aus der Existenz von Einwegfunktionen folgt zwar P!=NP, aber die umgekehrte Richtung ist noch nicht bekannt. Ylloh 03:48, 24. Feb. 2007 (CET)

Aus Faktorisierungsverfahren: Beim Faktorisierungsproblem für ganze Zahlen ist nicht bekannt welcher Komplexitätsklasse es angehört.--Spid 16:01, 8. Mär. 2007 (CET)

Algorithmus für eine NTM könnte in etwa so aussehen:

• Zwei natürliche Zahlen $a,b~|~a<{\sqrt {n}},b>{\sqrt {n}}$ aufbauen.
• $c=a\cdot b$ berechnen.
• Testen ob $c=n$. Wenn ja, a ausgeben, in einen Endzustand wechseln und halten. Sonst außerhalb vom Endzustand halten.

Alles drei keine schwierigen Probleme. Die NTM wird nur dann in einen Endzustand kommen, wenn sie das richtige a und b gewählt hat. Und dafür braucht sie auch nur maximal Polynomialzeit. Könnte eine DTM nun dasselbe in Polynomialzeit tun, wäre das Faktorisierungsproblem "lösbar" und z.B. RSA geknackt. Außer natürlich, das wir hier ein zu hohes Polynom haben.

--84.142.29.215 10:16, 17. Mai 2007 (CEST)

1. Stimmt, Faktorisierungsverfahren sollte bei Gelegenheit auch mal überarbeitet werden, natürlich liegt es in NP. Höchstens ist nicht bekannt, ob NP die untere Schranke für das Faktorisierungsproblem ist. Die von mir zitierte Formulierung dort ist irreführend.
2. Die public-key-Aussage ist dennoch problematisch, allein schon praktische Unlösbarkeit von NP-Lösungsalgorithmen. Gemeint ist wohl NP\P. Public-key baut darauf auf, dass das Faktorisierungsproblem entweder "ein hohes Polynom hat", oder gar nicht in P liegt. Für letzteres wäre P!=NP die Voraussetzung.

Spid 19:47, 18. Mai 2007 (CEST)

PS: siehe dazu auch Rivest-Cryptography, oder Papadimitriou-retrospective:
It is now common knowledge among computer scientists that NP-completeness is largely irrelevant to public-key cryptography, since in that area one needs sophisticated cryptographic assumptions that go beyond NP-completeness and worst-case polynomial-time computation [19]; furthermore, cryptographic protocols based on NP-complete problems have been ill-fated.--Spid

Überprüfbarkeit der Lösung

Ich bin mit der folgenden Formulierung unzufrieden: „Es stellt die Frage, ob Probleme existieren, für die eine gegebene Lösung leicht überprüft werden kann, das Finden einer solchen Lösung jedoch extrem schwierig ist,“ denn so stimmt das einfach nicht. Es gibt durchaus NP-vollständige Probleme, die sich mithilfe linearer Programierung (in exponentieller Zeit) lösen lassen. Durch die Formulierung des dualen Problems bekommt man aber die Möglichkeit, die Korrektheit dieser Lösung in polynomieller Zeit auf Optimalität zu überprüfen (starker Dualitätssatz). Laut der obigen Aussage wäre das der Beweis für P=NP. Man sollte in der Formulierung klarstellen, dass es sich um ein Entscheidungsproblem handelt.--Wolf. 11:54, 18. Feb. 2008 (CET)

Die Frage bei der linearen Programmierung ist nicht, ob eine Lösung in polynomieller Zeit überprüft werden kann, sondern ob eine Lösung tatsächlich nur in exp. Zeit gefunden werden kann. Bewiesen ist das nicht.--88.66.254.201 20:33, 23. Feb. 2008 (CET)

Meine Bemerkung war Quatsch. Nur ILPs können überexponentielle Zeit beanspruchen.--Wolf. 17:20, 16. Mai 2008 (CEST)

Das klingt ja nach P=NP

Da es jedoch in den vergangenen Jahrhunderten noch nicht gelungen ist, auch nur einen einzigen dieser Algorithmen zu finden, ist es zweifelhaft, dass nach dem Existenzbeweis umgehend ein Polynomialzeit-Algorithmus für diese Probleme gefunden würde.

das klingt imo so, als wäre schon klar, dass P=NP ist und man nurnoch einen entsprechenden algorithmus sucht...

Der ganze Satz ist IMHO Unsinn. Wenn für ein NP-Vollständiges Problem gezeigt würde, dass es in P liegt, wären mittels Polynomialzeitreduktion sofort alle Probleme aus NP in Polynomialzeit berechenbar. --DownAnUp 19:36, 25. Jan. 2010 (CET)

Es gibt durchaus die Möglichkeit, dass ein Beweis für P = NP in hohem Maße nicht-konstruktiv ist - so dass zwar die Gleichheit P = NP zu zeigen, ohne einen expliziten Algorithmus anzugeben. Das ist eine mathematische Möglichkeit die noch nicht auszuschließen ist (ebenso wie die Unabhängigkeit in ZFC, was man lax ausgedrückt wohl als Super-GAU der theoretischen Informatik bezeichnen könnte...). Ich habe den Artikel entsprechend erweitert --RedZiz 20:45, 27. Jan. 2010 (CET)

Unabhängigkeit kann ja wohl nicht sein, denn P ist Teilmenge von (oder gleich) NP. --Bri B. 12:04, 15. Feb. 2010 (CET)

[Falsches Beispiel Türme von Hanoi]

Das Beispiel der Türme von Hanoi ist falsch. Das ist kein Entscheidungsproblem, d.h. die Antwort ist nicht ja oder nein. Das Problem der Türme von Hanoi macht aber deutlich, warum man sich auf Entscheidungsprobleme beschränkt. Bei den Türmen von Hanoi wird die Ausgabe (=Zugfolge) exponetiell lang. Es ist aber einfach möglich, jede Beliebige Ausgabestelle zu berechnen.

Dem kann ich nur zustimmen. Das Problem der Türme von Hanoi gehört zu der Klasse der sogenannten exponentiellen Problemen (EXP-Probleme). -- H007A 14:32, 24. Mai 2009 (CEST)

Beweis für P≠NP ?

Hallo,

ich habe kürzlich bei arxiv.org ein interessantes Paper entdeckt, das angeblich Beweist, dass P≠NP gilt. siehe hierzu: http://arxiv.org/abs/0810.5056

Da theoretische Informatik dieser Tiefe für mich ein undurchsichtiger Symbolsalat ist wollte ich mal Fragen ob es jemanden gibt, der sich mal hiermit Befassen könnte. Es wäre auf jeden Fall wichtig dieses Paper, und das Review hierzu im Auge zu behalten und im Wikipedia-kontext mit einzuarbeiten...

CYA...

Diese angeblichen Beweise gibt es ziemlich oft und sollten nicht weiter ernst genommen werden. Meist sind sie im Ansatz fehlerhaft, was in letzter konsequenz zu fehlerhaften Resultaten führt. Sollte ein solcher Beweis tatsächlich korrekt sein, würde das sicher durch die einschlägigen Medien gehen.

Da steht klipp und klar, dass es P = NP nur in einem erweiteren logischen Axiomsystem gilt. Der Autor redet nicht davon, dass P = NP im normalen ZFC-Axiomensystem gelten soll. Von daher ist dieses Paper wahrscheinlich korrekt, aber bestenfalls ein Baustein im Gebäude der theoretischen Informatik, welches hier nicht weiter vertieft werden muss.

Ich bitte darum, wenigstens die Beschreibung des Papers richtig zu lesen, insofern man sie verstehen kann, bevor hier zu spekulieren. --RedZiz 14:04, 1. Dez. 2009 (CET)

P-NP-Problem in der Kryptologie

Entgegen verbreiteten Fehleinschätzungen ist das P-NP-Problem dennoch kryptologisch eher unbedeutend.

Unbedeutend würde ich das nicht nennen, nachdem es für viele Lösungen in der Kryptographie eine notwendige (wenn auch nicht hinreichende) Voraussetzung ist. 85.124.63.18 20:24, 18. Jan. 2009 (CET)

Naja, viele Probleme in der Kryptographie liegen garnicht in NP, von daher ist die P=NP Frage dafür in der Tat eher unbedeutend. Schönen Gruß --DownAnUp 19:37, 25. Jan. 2010 (CET)

Man korrigiere mich bitte, insofern ich etwas falsch verstehe. Aber die gegenwärtige theoretische Kryptografie basiert (wie im Artikel angedeutet) auf der angenommen Existenz von Einwegfunktionen, wie z.B. die Integermultiplikation. Diese ist jedoch z.B. schon in NP ( man rät nicht-deterministisch die Lösung, und verifiziert diese dann). Im Falle P=NP wären viele Primfaktorisierungsbasierte Verfahren der Kryptografie ihrer theoretischen Grundlage beraubt. --RedZiz 20:55, 27. Jan. 2010 (CET)

Falsch, DownAnUp, jedes asymmetrische Verfahren kann prinzipbedingt per NP-Algorithmus geknackt werden, da ein NP-Algorithmus alle geheimen Schlüssel gleichzeitig probieren kann, das verifizieren des richtigen Schlüssels ist in P möglich. --Erlenmayr 20:39, 1. Mai 2010 (CEST)

Lösung von Telpiz

Miron Telpiz hat einen Beweis publiziert, dass P=NP: Sigma-notation and the equivalence of P and NP classses. In: Journal of Information and Organizational Sciences, 2005 (29), 2, 1-12. --188.61.47.126 21:41, 27. Jul. 2010 (CEST)

"Weiterhin ist die Klasse P vollständig in EXP enthalten."

Wenn P mit Laufzeit n^k vorgestellt wird und EXP mit laufzeit 2^n, so wie im Artikel, so ist das wirklich nicht einleuchtend. Erst ein Klick auf den EXP(TIME) Artikel offenbart die Definition von 2^(n^k).

Sollte man vielleicht korrigieren?!? Kann sein das ich auch nen Denkfehler mache hier .. grus

--88.72.192.123 10:32, 20. Aug. 2010 (CEST)

Kryptologie

Ist es so, dass die für asymmetrische Verschlüsselung relevanten Primzahlzerlegungsprobleme erwiesenermaßen NP-vollständig sind? Im Artikel wird dies unter Praktische Relevanz implizit unterstellt. --Joachim Pense (d) 11:05, 27. Aug. 2010 (CEST)

Wenn dem nicht so wäre, wären Verschlüsselungen in Polynomialzeit knackbar. Es ist also anzunehmen, dass sie NP-vollständig sind, allerdings existiert nach meinem Kenntnisstand kein Nachweis. Vielleicht findet ja irgendwann jemand einen solchen Test bzw. Algorithmus dafür. Oder habe ich deine Frage falsch verstanden? --84.58.243.93 12:30, 27. Aug. 2010 (CEST)

Sie wären dann in Polynomialzeit knackbar, wenn jemand einen polynomialen Knack-Algorithmus gefunden hat. Daraus, dass noch keiner einen gefunden hat, folgt noch nicht die Zugehörigkeit zur Klasse der NP-Vollständigen Probleme. Deine Vermutung, dass für die NP-Vollständigkeit kein Nachweis existiert, teile ich auch; allerdings wird man aus dem Artikel schließen, es existiere so ein Nachweis. --Joachim Pense (d) 12:39, 27. Aug. 2010 (CEST)

Es gibt sehr wenige Probleme, deren NP-Vollständigkeit nachgewiesen ist, deswegen ist auch Karps Sammlung der 21 so besonders. Jeder weitere Nachweis einer NP-Vollständigkeit ist ein Baustein zum Beweis von P ≠ NP. Dies wird aus dem Artikel nicht ganz klar. Gruß nach Mainz --84.58.243.93 13:55, 27. Aug. 2010 (CEST)

Lösbarkeit in NP

Die Komplexitätsklasse NP ist die Menge aller von nichtdeterministischen Turingmaschinen in Polynomialzeit lösbaren Probleme.

Hierbei ist zu beachten, dass "Lösbarkeit" in NP und P unterschiedlich defniert ist. NP-lösbar heißt, dass mit einer nichtdeterministischen Maschine in polynomieller Zeit festgestellt werden kann, ob ein Wort zu einer Sprache gehört. Für eine Zeichenfolge, die kein Wort der Sprache ist, wird damit nichts gesagt. Für das Lösen von Problemen formuliert heißt dies, dass es bei P um das Finden von Lösungen (deterministisch in polynomieller Zeit) geht, bei NP um die Überprüfung einer Lösung (nichtdeterministisch in polynomieller Zeit). --Bri B. 12:14, 15. Feb. 2010 (CET)

Es hat sich etwas getan: P != NP möglicherweise bewiesen

Siehe http://www.heise.de/newsticker/meldung/P-NP-moeglicherweise-bewiesen-1052857.html

evtl. kann jemand, der Ahnung hat, das in den Artikel einarbeiten.--91.12.44.219 20:30, 9. Aug. 2010 (CEST)

Das steht schon seit 18 Uhr im Artikel, ist aber so noch keine Sensation. Beweise für P != NP wie das Gegenteil gibt es wie Sand am Meer, allein kommen die wenigsten davon von jemandem, der sich damit wirklich auskennt. Der hier schon, es hat ihn sich allerdings noch niemand so richtig ansehen können. Bis man dazu mehr sagen kann, werden noch einige Monate ins Land gehen. --YMS 23:36, 9. Aug. 2010 (CEST)

Scheint sich erledigt zu haben: Julie Rehmeyer: Crowdsourcing peer review. In: ScienceNews. 9. September 2010, abgerufen am 11. September 2010. 

{{Internetquelle|url=http://www.sciencenews.org/index/generic/activity/view/id/63252/title/Crowdsourcing_peer_review|titel=Crowdsourcing peer review|autor=Julie Rehmeyer|datum=2010-09-09|werk=ScienceNews|zugriff=2010-09-11}}

--Eorhim 20:29, 11. Sep. 2010 (CEST)

Was ist eine Turingmaschine der Größe n?

Für mich unverständlich ist folgender Nebensatz: "z. B. die Frage, ob eine Turingmaschine der Größe n auf einer Eingabe der Größe n innerhalb von 2^n Schritten anhält oder nicht". Was ist eine Turingmaschine der Größe n? Sofern ich weiß, ist die Fragestellung völlig unabhängig von der (für ein gegebenes Problem) konstanten "Größe" (d.h. der Anzahl der Zeilen der Zustandsübergangstafel) der Turingmaschine. Die "Größe" ist immer als konstant anzusehen. 93.128.113.27 15:12, 30. Aug. 2010 (CEST)

Du musst hier zwei Turingmaschinen unterscheiden: Zunächst hast du die TM, die diese Variante des Halteproblems lösen soll; deren Größe ist konstant und für die Komplexität unwichtig. Aber als Eingabe bekommt sie, neben einem Wort $w$, die Codierung einer weiteren TM, für die geprüft werden soll, ob sie (auf $w$) in $2^{n}$ Schritten anhält. Da diese TM eben auch ein Teil der Eingabe ist, ist deren Größe für das Problem relevant. Thomas5388 06:13, 15. Okt. 2010 (CEST)

Kurze Laufzeit vs. kurze Zeit

Der folgende Abschnitt stimmt meines erachtens so nicht: "Viele praktische Anwendungen für NP-vollständige Probleme, wie zum Beispiel das Problem des Handlungsreisenden, das Rucksackproblem oder das Problem der Färbung von Graphen, wären im Fall P = NP theoretisch optimal in kurzer Zeit lösbar"

Unter "kurzer Zeit" verstehe ich, je nach Kontext, Sekunden, Minuten, Tage oder Jahre. Sollte P = NP sein und der deterministische Algorithmus für ein Problem aus NP in O(n^1.000.000.000) sein, dann könnte eine optimale Lösung mit Sicherheit nicht in "kurzer Zeit" zu finden sein. Selbst bei sehr kleinen Eingabegrößen hätte ein solcher Algorithmus, obwohl er in P liegt, wohl eine Laufzeit die Länger wäre als das Alter des Universums. Das dürfte wohl in jedem Kontext als "lang" gelten.

Mir fällt allerdings keine gute Umschreibung ein. Korrekt wäre es zu sagen, dass im Falle P = NP ein Problem aus NP (z.B. Handlungsreisende, Rucksackproblem, ...) ab einer gewissen Eingabegröße immer schneller laufen würde als der Trivialansatz (also Bruteforce alle Routen durchgehen beim Handlungsreisenden). Wie groß diese Eingabegröße werden müsste, hängt dabei aber vom dem (theoretischem) Algorithmus ab, der ein Problem aus NP in polynomieller Zeit lösen könnte. Es kann also sein, dass es überhaupt nicht praxisrelevant ist, ob P = NP, weil der Algorithmus in P dennoch extrem langsam ist und man immer noch auf Heuristiken zurückgreifen müsste. --MartinThoma 13:46, 12. Dez. 2011 (CET)

Wie "gut" ist dieser Beweisversuch?

Im Artikel heißt es:

Am 6. August 2010 schickte der bei Hewlett-Packard angestellte Mathematiker Vinay Deolalikar einen möglichen Beweis für P ≠ NP an verschiedene Forscher.[3] Zwei Tage später tauchte die Vorabversion des Beweises im Web auf. Nach einigen Tagen behauptete Neil Immerman, zwei fatale Fehler in dem Beweis gefunden zu haben.[Quelle]

Es fehlt die Information, ob andere Experten Immerman zustimmen oder nicht. Das würde Aufschluss darüber geben, ob dieser Versuch "ganz gut" ist, oder ob er tatsächlich unbrauchbar, weil grundlegend fehlerhaft ist. Soweit ich den Artikel sehe spricht einiges dafür, dass Immerman recht hat, denn Deolalikar hat den Angriffen auf seine Ausführungen scheinbar nichts entgegenzusetzen. --88.130.96.57 04:29, 3. Feb. 2012 (CET)

der beweis ist tot, aber dennoch interessant. ich habe einen link zu einem video eingebaut, in dem das ganz gut erklaert wird. --Mario d 12:31, 3. Feb. 2012 (CET)

Cool, danke! --88.130.96.57 17:07, 3. Feb. 2012 (CET)

Gedankensprung zwischen "P und NP" und "Lösung des Problems"

Für mich als nicht vorbelasteten Leser ist am Ende des Abschnitts "P und NP" annähernd klar was ein NP-Problem ist. Die unmittelbar folgende Verwendung des Begriffs NP-vollständiges Problem kommt jedoch überraschend. Es wäre sehr schön, wenn an dieser Stelle das Konzept der Vollständigkeit kurz eingeführt werden könnte.

--217.110.199.118 12:15, 27. Feb. 2012 (CET)

ich habe mich mal daran versucht. --Mario d 13:47, 27. Feb. 2012 (CET)

Geschichte des Problems

Die erste Formulierung der Frage erfolgte durch Kurt GÖDEL in dessen Brief an John v NEUMANN vom 20.03.1956. (Quelle: siehe Vortrag von Prof. Michael SIPSER im Clay Institut, zu sehen auf Youtube "Beyond computation" Minute 25:33 und weiter) -- Bellafont 06.04.2013 (23:02, 6. Apr. 2013 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

Ich habs mal eingefügt.--Claude J (Diskussion) 00:03, 7. Apr. 2013 (CEST)

Mögliche Lösung?

Ist diese eine korrekte Lösung des Problems? http://arxiv.org/abs/1011.3944 (nicht signierter Beitrag von 2003:45:CB0E:D642:506A:F9BD:3A24:7F41 (Diskussion | Beiträge) 21:51, 17. Jun. 2014 (CEST))

Die Versuche der Fachwelt, den Ansatz des Autors V. F. Romanov nachzuvollziehen bzw. zu überprüfen, sind bisher gescheitert, siehe die Diskussionen in [2] und [3]. --TeesJ (Diskussion) 08:50, 18. Jun. 2014 (CEST)

Turingmaschiene der Größe n?

"ob eine Turingmaschine der Größe n auf einer Eingabe der Größe n ..."

Tipp/Kopierfehler? Ich weiß nicht was die Größe einer Turingmschine sein sollte - der Artikel zur Turingmschine kennt zumindest keine größe. Bitte Klären. (nicht signierter Beitrag von 91.39.80.158 (Diskussion) 18:43, 23. Feb. 2016 (CET))

Halteproblem in EXP

Die Anführung des Halteproblems als Beispiel für Probleme die zwar in EXPTIME aber nicht in P lösbar sind ist falsch. Im Artikel heißt es korrekterweise, dass in diesem Falle als obere Schranke für die notwendige Zeit zur Lösung des Problems ein exponentieller Zeitaufwand gelten würde. Tatsächlich ist das Halteproblem bewiesenermaßen jedoch nicht lösbar. Eine (obere) Zeitschranke lässt sich somit nicht festlegen. Folglich ist auch die Anführung des Halteproblems an dieser Stelle nicht sinnvoll, da somit eine (generell nicht existierende) Lösbarkeit in EXP suggeriert würde. Die Beantwortung der Frage, ob ein Programm innerhalb von 2^n Schritten hält - wie sonst im Artikel beschrieben - liegt wiederum tatsächlich in EXP. Dabei handelt es sich jedoch nicht um die allgemeine Form des Halteproblems. --StepTiger (Diskussion) 22:20, 11. Okt. 2016 (CEST)

Stimmt das?

Kann sich ein Experte diesen Edit [4] bitte anschauen? Stimmt das? LG --†ex†kon†rolle • ⇨℡ 11:11, 8. Mai 2017 (CEST)

Die IP hat recht, dass ein "nicht entscheidbares" Problem auch keinen Algorithmus besitzen kann, dass es in EXP-Zeit entscheidet.

Du, lieber Textkontrolle, hast recht, dass die beiden Abschnitte insgesamt zu löschen, too much war - die restlichen Sätze drumherum sind nicht falsch - nur das Halteproblem war ein "Nicht-Beispiel", man müsste ein anderes anstatt ihm einsetzen X-) ...

--arilou (Diskussion) 12:07, 8. Mai 2017 (CEST)

Anscheinend gelöst?

Norbert Blum (Uni Bonn) hat wohl einen Beweis für P ungleich NP erbracht.(nicht signierter Beitrag von 2a02:8109:9540:3cd4:4848:da7e:c2aa:2e3 (Diskussion) )

Du meinst N. Blum, A Solution of the P versus NP Problem, Arxiv Preprint 2017. Resonanz ?--Claude J (Diskussion) 22:33, 14. Aug. 2017 (CEST)

Hab Norbert Blums Preprint unter Beweisversuche erwähnt.--Claude J (Diskussion) 11:45, 15. Aug. 2017 (CEST)

Anscheinend wieder entfernt, vielleicht sollte man wirklich etwas abwarten, aber das Argument dass es nicht in einer Peer Review Zeitschrift veröffentlicht wurde gilt gleichermaßen für andere bekannte Beweisversuche (einschließlich dem im Artikel Erwähnten von Deolalikar von 2010) und der Abschnitt heisst "Beweisversuche". Hat inzwischen schon einige Aufmerksamkeit gefunden (veröffentlicht erst am 14. August, auch wenn 11. August datiert). Blog Luca Trevisan, Blog Villatoro (spanisch), Alon Amit, Quora, und Fachfremde Lubos Motl, John Baez, Spektrum d. Wiss.--Claude J (Diskussion) 11:56, 16. Aug. 2017 (CEST)

"peer-reviewd" soll keine notwendige Bedingung dafür sein, dass es im Artikel aufgenommen werden kann. Wenn sich die Relevanz anderweitig belegen lässt, dann kann das damit gemacht werden. Zu dem Zeitpunkt, an dem die Stelle in den Artikel geschrieben wurde, war das jedenfalls noch nicht der Fall, deshalb habe ich das wieder entfernt. Und im Moment fehlen uns wirklich noch Aussagen zur Relevanz, also ob das Paper tatsächlich irgendeinen Beitrag leistet, z.B. eine neuartige Beweistechnik, ein interessanter Ansatz etc. Bisher haben wir nur die Information, dass einige Fachkollegen es grundsätzlich für einen legitimen Beweisversuch halten (von dem es aber schon viele gab). --TheRandomIP (Diskussion) 19:27, 16. Aug. 2017 (CEST)

vielleicht sollte man abwarten, was die Fachwelt dazu sagt, das kann erfahrungsgemäß Monate bis Jahre dauern. Immerhin hat die FASZ am 27.8.2017 S.58 "Die Macht des Nein - Ein Bonner Mathematiker will bewiesen haben, dass P # NP", von Ulf Rauchhaupt. Vielleicht könnte ein geübter Wikipedianer das als Literaturzitat im Artikel vermerken, ich bi da leider erst am ANfang. Danke & Grüße --84.176.141.112 15:34, 1. Sep. 2017 (CEST)

Inzwischen hat er den Beweis zurückgezogen da fehlerhaft, siehe seinen Kommentar in Arxiv.--Claude J (Diskussion) 15:37, 1. Sep. 2017 (CEST)

Nash's Brief von 1950 an die NSA?

"Eine weitere frühe Formulierung findet sich in einem Brief von John Forbes Nash 1950 an die National Security Agency, wobei es um Kryptographie ging." - wie kann Nash 1950 an die NSA geschrieben haben, wenn die NSA erst 1952 gegründet wurde? Entweder wurde der Brief nach 1952 geschriben oder er ging nicht an die NSA (dann wohl eher an die Vorläuferbehörde AFSA) --213.61.24.235 10:30, 16. Sep. 2019 (CEST)

In der angegebenen Referenz steht zwar 1950, und aus diesem Jahr stammen Vorschläge von Nash, die später von der NSA ausgewertet wurden, der Brief stammt aber von 1955 und ist bei der NSA Online. Der Abschnitt ist übrigens beginnend mit "Now my general conjecture is as follows .." auf S. 4 des Briefes.--Claude J (Diskussion) 10:51, 16. Sep. 2019 (CEST)

Beispiel für NTM

Da wurde jetzt folgendes Beispiel für NTM (nichtdeterministische Turingmaschine) eingefügt: "Eine NTM kann zunächst alle denkbaren Lösungen erzeugen, wobei sie ihren Rechenweg verzweigt. In jedem Zweig wird anschließend eine der Lösungen deterministisch (ohne weitere Verzweigungen) geprüft, um zu entscheiden, ob eine Lösung existiert bzw. um die richtige Lösung zu bestimmen und auszugeben. Z. B. lässt sich das Problem, eine gegebene Zahl $N$ zu faktorisieren, dadurch lösen, dass man zunächst alle möglichen Teiler $d$ größer 1 und kleiner $N$ erzeugt. Anschließend wird jeweils geprüft, ob die Division $N:d$ ohne Rest aufgeht." Das ist doch immer noch eine deterministische Turingmaschine. Der wesentliche Punkt ist doch dass es mehrere Möglichkeiten bei mindestens einem der Rechenschritte gibt (Verzweigung), welchen Weg die Maschine geht ist aber nicht durch den Anfangsinput und die bis dahin erzielten Rechenergebnisse bestimmt, sondern z.B. durch Würfeln (Zufall). Im vorigen Absatz ist auch nicht korrekt, dass eine NTM zu jedem Zeitpunkt mehrere Möglichkeiten hat, sie kann vollkommen deterministisch sein bis auf einen einzigen Rechenschritt.--Claude J (Diskussion) 08:49, 5. Jun. 2020 (CEST)

"nichtdeterministisch" heißt hier nicht unbedingt "zufällig". Die Arbeitsweise einer NTM kann man auf zwei Arten interpretieren, wie es auch im Artikel Nichtdeterministische Turingmaschine steht: Entweder so, dass sie zufällig einen der Rechenwege wählt, oder so, dass sie alle möglichen Wege parallel verfolgt. Wenn eine NTM ein Problem aus NP löst, dann verhält sie sich gemäß der zweiten Interpretation.
Dass die NTM in jedem Schritt mehrere Möglichkeiten haben muss, stimmt allerdings nicht, das ist nicht gut ausgedrückt, ich ändere das mal.--Megatherium (Diskussion) 10:27, 5. Jun. 2020 (CEST)

Gut ich verstehe, dann sollte bei NP aber noch deutlicher gemacht werden (nebenbei wurde die formale Definition dort als unverständlich auf der Disk kritisiert), dass das nicht einfach ein konventioneller Parallelrechner ist (z.B. stackexchange). Die Rechenwege nach der Verzweigung kommunizieren nicht miteinander.--Claude J (Diskussion) 10:55, 5. Jun. 2020 (CEST)

Da ging irgendwie was durcheinander. Die Formulierung im Artikel war wenig hilfreich und hatte keinen Erkenntnisgewinn. --TheRandomIP (Diskussion) 00:15, 6. Jun. 2020 (CEST)

Der wesentliche Punkt, der hier Verständnisschwierigkeiten bereitet ist doch wohl die Erklärung, was die Klasse NP ist (worauf dann NP-Vollständigkeit bzw. NP-Schwere definiert werden kann, das die eigentlich interessierenden Beispiele liefert). Wenn du ohne weitere Erklärung den Satz hineinsetzt, es wäre kein real existierender Computer als Beispiel für NTM bekannt und auch keine Idee, wie ein NTM-Computer realisiert werden könnte, hast du das Problem dass der Durchschnitts-Leser nicht versteht wozu man sich überhaupt damit beschäftigt. Ich sehe das so (aber vielleicht liege ich ja falsch): in der realen Welt muss noch etwas von Außen zu der abstrakten Definition hinzukommen, um den Rechenweg nach der Verzweigung festzulegen, entweder eine Quelle für Zufallszahlen, "Willensfreiheit" oder eben die Möglichkeit, angepasst an das Problem beliebig viele Kopien neuer Turingmaschinen zu erstellen, die alle Verzweigungsmöglichkeiten parallel abarbeiten. Da sie nicht miteinander kommunizieren muss dann ein Beobachter von Außen die Ergebnisse vergleichen. Vielleicht sollte man aber gleich in der Einleitung mit einem der NP-vollständigen Beispiele anfangen (am verständlichsten Problem des Handlungsreisenden, TSP) und die Frage so formulieren ob TSP in Polynomzeit lösbar ist.--Claude J (Diskussion) 07:24, 6. Jun. 2020 (CEST)

Ich habe mal eine gute Veranschaulichung für das Problem der Wegwahl bei der Verzweigung im Suchbaum gelesen. Die NTM "rät" einfach den nächsten Weg, und sie "ratet/rät" immer richtig (wie etwa ein Orakel ?). Traugott (Diskussion) 00:04, 11. Jun. 2020 (CEST)

Ist der Artikel allgemeinverständlich?

Also ich spiele wirklich nicht gerne den Buhmann, aber ich weiß mit dem Artikel nichts anzufangen und ich bin mir sicher, dass es nicht nur mir so geht. Da wird man sich erstmal fragen „Wo ist da jetzt das Problem?“ oder „Wie kommt man auf sowas?“. Der Artikel strotzt nur so von Formeln und komplizierten Formulierungen (was ist denn nun P?). Ich habe mir den spanischen und den englischen Artikel angeschaut, die scheinen mir etwas verständlicher. Könnte da jemand etwas machen?--Chris1202 (Diskussion) 15:30, 6. Mär. 2020 (CET)

Schön wäre es, aber wenn man den Artikel verständlicher machen will kommt immer irgendein schlauer Theoretiker daher der da ein Haar in de Suppe findet und deswegen kann da nichts einfach formuliert werden. Nicht wahr @Megatherium:? --TheRandomIP (Diskussion) 21:16, 6. Mär. 2020 (CET)

Habe mal ein weniger abstraktes Beispiel verwendet. Die Beschreibung in der englischen Wikipedia ist fehlerhaft. Klar, es gibt Algorithmen, die exponentieller Zeit ablaufen. Mag sogar sein, dass Sudokualgorithmen dazugehören. Hier geht es aber um polynomielle Zeit auf zwei verschiedenen Turingmaschinen. Und es ist bis heute unklar, ob deren Komplexitätsklassen nicht sogar gleich sind. P ist eine Klasse von Problemen, die auf einer deterministischen Turingmaschine in Polynomialzeit gelöst werden können. Das steht bereits da. Die Frage, was eine deterministische Turingmaschine ist oder was Polynomialzeit, wird durch Verweis geklärt. Es hat wohl seinen Grund, warum das Problem im tertiären Bildungsbereich behandelt wird. --Tattoo (Diskussion) 00:59, 10. Mai 2020 (CEST)

Das mag wohl sein, aber entbindet meiner Meinung nach dennoch nicht von einer verständlicheren Formulierung für Otto Normalverbraucher.--195.243.201.20 19:04, 24. Mai 2020 (CEST)

Liebe IP, wenn du die Formulierung genau bezeichnest, bei der du eine Entbundenheit des Autors vermutest, ließe sich deine Anmerkung ggf. produktiv umsetzen. --Tattoo (Diskussion) 07:56, 14. Jun. 2020 (CEST)

Ich musste den Artikel in der englischen Wikipedia lesen um ihn (möglicherweise falsch) zu verstehen

Hier in der Deutschen ist er so geschrieben daß man ein Mathematikstudium braucht um zu verstehen worum es überhaupt geht. Im englischen Artikel habe ich dagegen sofort verstanden worum es geht. Das lässt schon auf die Güte der Formulierungen schliessen - angreifbar oder nicht - ich glaube hier kommen wir wieder zu den wundersamen Formulierungen was Wikipedia alles nicht ist und ich würde sagen es ist auch kein Mathe Lehrbuch sondern sollte Menschen mit durchschnittlicher Bildung zumindest ermöglichen grundlegend zu verstehen was gemeint ist.(nicht signierter Beitrag von MasterKyodai (Diskussion | Beiträge) )

Die Einleitung ist doch gerade auf Allgemeinverständlichkeit hin angepasst worden. Einfacher gehts nicht mehr. Für weitere Anpassungen musst du schon konkret auf eine Stelle hinweisen, die Verständnisschwierigkeiten bereitet.--Claude J (Diskussion) 07:49, 3. Jun. 2020 (CEST)

Die Einleitung habe ich auf deinen Hinweis hin mal umformuliert. Vielleicht kannst du Feedback geben, ob es besser verständlich ist. --TheRandomIP (Diskussion) 10:51, 3. Jun. 2020 (CEST)

Die Geschwindigkeit ist ggf. von der Maschine abhängig, auf der gerechnet wird. Wenn der Begriff schnell nicht wohldefiniert ist, kann die Einleitung alles bedeuten und erklärt nichts. Hier genügt scheinbar, dass der Rechenaufwand durch eine Polynomfunktion beschränkt ist. Das ist er auf einer NTM per definitionem, das Problem ist offenkundig dennoch nicht gelöst. --Tattoo (Diskussion) 08:17, 14. Jun. 2020 (CEST)

Ich habe hier leider mal etwas Richtiges aus Irrtum entfernt.

Ich liefere das entsprechende Diff nach. Traugott (Diskussion) 14:32, 12. Jun. 2020 (CEST)

Verständlichkeit

Die Verständlichkeit des Artikels ist nicht existent weshalb man da noch dran arbeiten MUSS. Leider fehlt mir das dazugehörige Fachwissen weshalb das wer anders machen muss LeoFirestorm08 (Diskussion) 21:30, 7. Jan. 2023 (CET)

Kannst du das mal näher ausführen? Wenn du konkrete Stellen nennst, die du nicht verstehst, kann man sich diesen annehmen. Ansonsten müsste man hier Rätselraten was du nun nicht verstanden hast. --TheRandomIP (Diskussion) 21:34, 7. Jan. 2023 (CET)

NP =/= P Beweis

NP =/= P ist mithilfe der Strengen Logik leicht zu beweisen.

Zur Einführung wird im folgenden Absatz die Behandlung des Modus ponens in der Strengen Logik (von Walther Brüning) dargestellt:

Die erste Prämisse ist eine Bedingung dyadischer (d. h. zwei Sachverhalte sind miteinander verbunden) Stufe (deshalb Großbuchstabe). Es handelt sich um einen Bedingungssatz. Die zweite Prämisse ist eine dyadisch verlängerte henadische (d. h. einen Sachverhalt betreffend) Formel (deshalb Kleinbuchstaben und Gleichstellen); ebenso die Konklusion. (Das fett geschriebene a geht in die Konklusion ein, weil das andere a der Gleichstelle von einem n blockiert wird.). Das hochgestellte c bedeutet condicio:

	1	2	3	4
	F G	~F G	F ~G	~F ~G
$F\supset ^{c}G$	u	u	N	u
$F$	a	u	a	u
$G$	a	a	u	u

Die Spalten sind nach den verschiedenen möglichen Kombinationen getrennt. Die Verlängerung der Geltungswertformeln der Prämisse $F$ bzw. der Konklusion $G$ ergibt sich durch die Einführung des jeweils zweiten Begriffes $G$ bzw. $F$. Ihr Wert bleibt deshalb bei der Erweiterung gleich (es bilden sich Gleichstellen). "a" – kurz für Affirmation (entspricht wahr); "N" – kurz für Negation (entspricht falsch); "u" – kurz für unbestimmt; "~X" – kurz für Komplement von X.

Das wäre also ein Beispiel für ein Bedingungssatz mit Konklusion. Nun kann man den Modus Ponens umdrehen, sodass $G$ und der Bedingungssatz eine Konklusion ergeben sollen:

	1	2	3	4
	F G	~F G	F ~G	~F ~G
$G$	a	a	u	u
$F\supset ^{c}G$	u	u	N	u
Die Konklusion enthält keine relevante Information.	u	u	u	u

--123qweasd (Diskussion) 01:11, 22. Aug. 2023 (CEST)

LOL. --Daniel5Ko (Diskussion) 01:27, 22. Aug. 2023 (CEST)

LOL. --123qweasd (Diskussion) 04:33, 22. Aug. 2023 (CEST)

Damit sind NP-Probleme bewiesen. P-Probleme wären mit beiden Bedingungssätzen (zugleich): notwendige und hinreichende Bedingung zugleich. --123qweasd (Diskussion) 11:28, 26. Aug. 2023 (CEST)

Die Konklusion aus dem Beweis für NP-Probleme ist folgendermaßen zu interpretieren: Eine eventuelle (affirmative oder negative) Bestimmung kommt auf der dyadischen Stufe als neue Information hinzu.123qweasd (Diskussion) 11:48, 26. Aug. 2023 (CEST)

Wie lässt sich nun ein NP-Problem lösen? Es geht nur mit der Einführung eines dritten Begriffs ($H$). Die Geltungswertstellen sind zu erweitern (triadische Stufe) und die Werte sind entsprechend zu verlängern:

	F G H	~F G H	F ~G H	~F ~G H	F G ~H	~F G ~H	F ~G ~H	~F ~G ~H
($F$$\supset ^{c}$ $G$) $\supset ^{c}$ $H$	u	u	u	u	u	u	N	u
~$H$	u	u	u	u	a	a	a	a
$F$	a	u	a	u	a	u	a	u
~$G$	u	a	u	a	u	a	u	a

Inwieweit eine Unterscheidung zwischen NP- und P-Problemen sinnvoll ist, ist eine metaphysische Frage (Denn die Information von $H$, respektive ~$H$, könnte genausogut in einen Bedingungssatz $F\subset ^{c}G$ einfließen). Rein logisch sind sie unterschiedlich zu behandeln.123qweasd (Diskussion) 10:35, 1. Sep. 2023 (CEST) 123qweasd (Diskussion) 10:37, 1. Sep. 2023 (CEST)

Es ist wahrscheinlich keine schwere Übung, sich zu überlegen, warum du für deine Erkenntnisse keinen Turing-Award bekommst, oder Verwandtes mit "Millenium Prize" statt "Turing-Award". Metaphysik spielt dabei überhaupt keine Rolle. --Daniel5Ko (Diskussion) 01:59, 3. Sep. 2023 (CEST)

„Individuelle Begriffe entziehen sich wegen ihrer komplexen Struktur der genauen logischen Analyse.“ Es geht dabei nur um die Sinnhaftigkeit, nicht um die formale Umschreibung. --123qweasd (Diskussion) 15:26, 3. Sep. 2023 (CEST)

Das habe ich dann leider nicht mehr geschrieben. --123qweasd (Diskussion) 15:47, 3. Sep. 2023 (CEST)

Weiters: $F$ lässt sich also nur gleichzeitig mit ~$G$ ableiten. Dadurch ergibt sich eine (exponentiell) längere Laufzeit eines Programmes gegenüber P-Problemen.

Was mir jetzt noch dazu einfällt: Ein (im Rahmen von $F\supset ^{c}G$) zufälliger Probieralgorithmus, könnte in P-Zeit ablaufen (weil es Angewandte Logik wäre), statistisch (durchschnittlich) wird er aber in NP-Zeit ablaufen.

Am Beweis (Stand: jetzt) würde es jedenfalls nicht liegen. Tut mir Leid, dass ich das Offensichtliche ausspreche. --123qweasd (Diskussion) 18:35, 3. Sep. 2023 (CEST)

Ich muss mich leider etwas korregieren: Die (exponentiell) längere Laufzeit ergibt sich nur indirekt aus ~$G$. Direkt ergibt sie sich aus "Existenz"-Bestimmungen. "In gewissen überschaubaren Zusammenhängen kann die e-Indizierung auch einfach dadurch ersetzt werden, daß man alle A-Stellen als existentiell bestimmt versteht." Bei P-Problemen ($F$) sind zwei A-Stellen in einer der Prämissen; Bei NP-Problemen (~$H$) sind es vier. Edit:123qweasd (Diskussion) 20:08, 5. Sep. 2023 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: --123qweasd (Diskussion) 14:11, 9. Okt. 2023 (CEST)