Diskussion:Satz von Cook

Ich habe den Artikel mal überarbeitet, bin aber damit nicht wirklich zufrieden, Limdul 01:37, 2. Dez 2004 (CET)

Einleitung

"Mit einem bekannten Vertreter der Klasse war der Nachweis für andere Probleme aus NP wesentlich einfacher zu führen, da bei ihnen nur noch die polynomielle Reduzierbarkeit auf SAT nachgewiesen zu werden braucht." Müsste es nicht andersrum sein? Ich kann doch alle Probleme aus NP auf SAT reduzieren, das macht sie noch nicht NP-vollständig... (nicht signierter Beitrag von 84.129.201.34 (Diskussion) 22:36, 25. Mär. 2011 (CET))

Beweisidee

Werde mich nach meinen letzten Beiden Prüfungen mal um den Beweis kümmern und versuchen den für "normal Sterbliche" zu erklären. Oder ist der Satz so speziell, dass ich ein Informatikstudium vorraussetzen kann. Im Prinzip sollte der Anspruch ja Verständnis für jedermann sein. --Unclefu

Ich bin mir leider nicht vollends sicher, würde aber behaupten, dass Schritt 6 so, wie er da formuliert ist, Determinismus bedeuten würde. Da müsste dann nämlich Übergangsrelation statt Übergangsfunktion stehen. Vielleicht habe ich es aber auch noch nicht verstanden.--JensVonZobel 09:45, 22. Feb. 2008 (CET)

Der Beweis bezieht sich auf eine randomisierte Turingmaschine und die hat Übergangsfunktionen $(\delta _{1},\delta _{2})$. Steht so aber auch nicht wirklich im Artikel.--82.207.240.59 20:27, 9. Aug. 2008 (CEST)

In dem Beweis sollte nochmal aufgezeigt werden, dass die Reduktion tatsächlich in polynomieller Zeit durchführbar ist. Zusätzlich sollte man noch argumentieren, dass SAT in NP liegt, denn sonst zeigt man doch nur die NP-Härte? -- 78.54.14.246 14:52, 23. Mär. 2012 (CET)

Ja das stimmt, beide Argumente fehlen. Was SAT ∈ NP betrifft, das sollte auf jeden Fall argumentiert werden. Was die Berechnung in Polynomialzeit betrifft, hier würde ich mich mit einem Hinweis begnügen, daß sich dies aus der (im Artikel nicht angegebenen) genauen Konstruktion der Formel erkennen lässt. Auf eine Argumentation würde ich hier verzichten, da das eine allzu technische Darstellung des Beweises erfordern würde. -- Carsten Milkau (Diskussion) 00:11, 4. Nov. 2012 (CET)

Karp und der Satz von Cook

Hat Carp 1972 wirklich die NP-Vollständigkeit von SAT gezeigt? Leider komme ich an das Paper im Moment nicht ran, aber es heißt immer, "Karp72 hat die NP-Vollständigkeit von 21 kombinatorischen Problemen gezeigt". Gehört da SAT dazu? Falls das stimmt, würde ich noch die Literaturangabe mit in den Artikel nehmen:

R. M. Karp. Reducibility among combinatorial problems, in Complexity of Computer Computations (J. W. Thatcher and R. E. Miller, eds.), Plenum Press, 1972.

Falls Karp nichts direkt mit dem Satz von Cook zu tun hat, gehört er natürlich auch nicht in diesen Artikel (aber z.B. in NP-Vollständigkeit)... --Esperantisto 11:38, 24. Feb 2005 (CET)

Im Buch Komplexitätstheorie von Ingo Wegner wird jedenfalls gesagt es wär der Beweis von SAT. Der Beweis den ich kenne passt eigentlich auch zu SAT. Die Anderen Probleme sind ja dann reduzierbar --Unclefu

In Nr. 8.4.6 (S. 178) von Papadimitriou: Computational Complexity klingt es jedenfalls gar nicht so. Dort wird erst Cooks Artikel zitiert, und dann Karps als "subsequent paper" bezeichnet.

Dann wird allerdings noch gesagt, dass Leonid Levin unabhängig davon von verschiedenen kombinatorischen Problemen zeigte, dass sie "universal for exhaustive search" seien, was leicht mit NP-Vollständigkeit identifiziert werden könne. Cooks Satz werde deshalb manchmal auch als Cook-Levin-Satz bezeichnet. Der Artikel ist

L. A. Levin. "Universal sorting problems," Problems of Information Transmission, 9, S. 265-266, 1973.

Klingt nicht unbedingt so, als hätte er gezeigt, dass SAT NP-vollständig ist, aber (unabhängig) zu zeigen, dass es NP-vollständige Probleme gibt, ist ja vielleicht auch wichtiger.

--Tian 22:56, 25. Feb 2005 (CET)

Nein, Karp hat lediglich die NP-Vollständigkeit weiterer Probleme über mehrere polynomielle Reduktionen gezeigt. IIRC bezieht er sich in seiner Arbeit explizit auf Cook, was die NP-Vollständigkeit des Erfüllbarkeitsproblems betrifft. --Carsten Milkau 17:58, 18. Mai 2009 (CEST)

"Man erzählt sich ..."

Kann man das nachprüfen? So ist es ein Gerücht und Wikipedia keien Gerüchteküche. Solange das nicht belegt wird sollten wir es entfernen. Stern 11:21, 27. Jan 2006 (CET)

Beweisskizze

"Beschreiben lässt sich eine randomisierte Turing-Maschine über die folgenden drei boolschen Variablen:..." Das sind ja nicht nur 3 Variablen sonder drei Mengen von Variablen. Sollte man besser irgendwie umformulieren, oder? JaK 17:19, 24. Mär. 2007 (CET)

RP != NP

„Jedes Problem der Klasse NP kann durch eine nicht-deterministische oder auch randomisierte Turingmaschine in polynomieller Zeit gelöst werden.“

Woher stammt diese Aussage? Erstens gibt es verschiedene Modelle, was "in polynomieller Zeit lösen" für probabilistische Turingmaschinen bedeutet, und zugehörige Komplexitätsklassen, z.B. RP, ZP und BPP. Zweitens ist meines Wissens bislang ein offenes Problem, ob eine dieser Klassen mit NP zusammenfällt, und vermutet wird allgemein eher das Gegenteil! --Carsten Milkau 18:08, 18. Mai 2009 (CEST)

Zustand

Der Artikel schon ein biss. merkwürdig. Ein Beweis der keiner ist, Merkwürdigkeiten bei den Aufzählungen und Formulierungen, was auch immer die ausdrücken wollen ein Beweis für SAT $\in$ NPC ist das jedenfalls nicht. Es wäre besser den Artikel in dieser Form gänzlich wegzuwerfen und einen neuen zu schreiben der weniger Fragen aufwirft. --95.91.58.156 16:27, 9. Mär. 2012 (CET)

Beweisskizze

Der erste Satz kann wohl so nicht stimmen. L eine Sprache ist und SAT ein Problem. (nicht signierter Beitrag von 95.91.62.194 (Diskussion) 22:48, 14. Mai 2012 (CEST))

NP heißt: deterministische Turingmaschine kann Lösung verifizieren

Der Satz in der Beweisskizze

Weil L in NP liegt, gibt es eine nichtdeterministische Turingmaschine M, welche in Polynomialzeit entscheidet, ob x zur Sprache L gehört.

müsste meines Wissens nach eigentlich

Weil L in NP liegt, gibt es eine deterministische Turingmaschine M, welche in Polynomialzeit entscheidet, ob x zur Sprache L gehört.

Der Artikel über NP stimmt mit meiner Ansicht im Absatz "Äquivalente Charakterisierungen", erster Satz überein: es heißt "deterministisch" und nicht "nichtdeterministisch". --79.226.15.80 14:09, 20. Sep. 2013 (CEST)