P-NP-Problem, die Zweite

Ich bitte um sachliche Kritik an meiner line of reasoning:

Ein Problem ist genau dann in NP, wenn es einen polynomiellen Algorithmus (in Bezug auf die Größe der Eingabedaten) gibt, der überprüft, ob eine gegebene Lösung korrekt ist.

Ein Problem ist genau dann in P, wenn es in NP ist und zusätzlich die Anzahl der Lösungen, die überprüft werden müssen, so dass mit hundertprozentiger Sicherheit die korrekte Lösung darunter ist, polynomiell ist (ebenfalls in Bezug auf die Größe der Eingabedaten).

Ich definiere:

Lösungsraum: ist die Anzahl der Lösungen, die es überhaupt geben kann, egal ob korrekt oder nicht.

Suchraum: ist die Anzahl der Lösungen, die unbedingt durchsucht werden müssen, damit mit hundertprozentiger Sicherheit die korrekte Lösung darunter ist (ohne Raten und ohne vorherige Kenntnis der korrekten Lösung).

Die Frage ist, ob es Probleme gibt, die in NP, aber nicht in P liegen.

Bekannt ist: Es gibt NP-vollständige Probleme; nur wenn ein NP-vollständiges Problem in NP, aber nicht in P liegt, gibt es Probleme, die in NP, aber nicht in P liegen.

Ein NP-vollständiges Problem ist k-SAT: Gegeben sind n boolesche Variablen (können die Werte wahr oder falsch annehmen), diese kommen in c Clauses (Disjunktionen) vor, jeweils k Variablen pro Clause; alle Clauses sind miteinander durch Konjunktion überprüft.

Ich möchte zeigen, dass der Suchraum bei k-SAT nicht polynomiell und daher k-SAT nicht in P enthalten ist.

Der Lösungsraum beträgt 2^n, da jede Variable entweder wahr oder falsch sein kann, also genau zwei Werte annehmen kann. Der tatsächliche Suchraum ist kleiner als 2^n, aber im allgemeinen Fall nicht polynomiell. Der Grund: Es gibt keine andere Möglichkeit vorzugehen, als einer Variablen einen Wert zuzuweisen und dann zu schauen, wie sich das auf die anderen Variablen auswirkt. Wenn k-SAT in P wäre, dann müsste es in jeder Formel die gleiche Anzahl von Variablen geben, deren Wert man festlegen muss, so dass sich die Werte aller anderen Variablen ergeben. Wenn das t Variablen sind, dann ist der Suchraum (n choose t). Wenn t konstant ist, ist das polynomiell. t ist aber nicht konstant. Vielmehr stellt die Anzahl der Clauses eine obere Schranke für t dar. t kann also unter Umständen so groß sein wie die Anzahl der Clauses. Da die Anzahl der Clauses bei k-SAT aber variabel ist, ist der Suchraum nicht polynomiell.

Das wären die Gedanken, die mir kurz durch den Kopf geschossen sind. Ich habe nämlich heute meinen 30. Geburtstag, und ein Gratulant hat mir gewünscht, dass ich dieses Jahr endlich das P-NP-Problem löse. Deswegen habe ich jetzt im Bett darüber nachgedacht, obwohl ich eigentlich schon längst schlafen sollte, weil es schon fast Mitternacht ist und ich morgen früh wieder arbeiten muss. Deshalb nehme ich mir jetzt nicht die Zeit, selbst genau darüber nachzudenken, ob bzw. wo ich einen Fehler gemacht habe. Wie gesagt, bitte ich um sachliche Kritik.

Vielen Dank für die Glückwünsche!

Zitat von Christoph R.

Du nimmst damit implizit bereits an, dass k-SAT in NP ist und du einen mehr als polynomiellen Teil des Suchraums durchsuchen musst. Du zeigst also: NP != P genau dann wenn NP != P.

Kannst du mir erklären, wie du das meinst? Mir ist nämlich nicht klar, was du damit meinst. k-SAT ist NP-vollständig - das ist allgemein bekannt bzw. wurde es schon vor Jahren/Jahrzehnten bewiesen. Wie ich erklärt habe, muss man bei Problemen, die in NP, aber nicht in P liegen, einen mehr als polynomiell großen Suchraum durchsuchen. Diese Behauptung ist nicht trivial. Eine zulässige Kritik wäre, dass ich diese Behauptung nicht bewiesen habe. Jedenfalls will ich zeigen, dass k-SAT einen mehr als polynomiell großen Suchraum erfordert - das würde (wenn vorige Behauptung wahr ist) P != NP beweisen. Dass k-SAT einen mehr als polynomiell großen Suchraum erfordert, ist keineswegs trivial. Ich bin mir auch nicht sicher, ob mein Versuch, das zu beweisen, hieb- und stichfest ist.

Zitat von Juggl3r

Ernstgemeinte Frage: Wie hast du das Informatikstudium eigentlich erfolgreich absolvieren können?!

Indem ich die Prüfungen bestanden habe, Diplomarbeit geschrieben habe - so, wie es jeder gemacht hat, der das Informatikstudium erfolgreich absolviert hat. Was veranlasst dich denn zu deinen Zweifeln? Ich habe das Informatikstudium übrigens sogar mit Auszeichnung abgeschlossen!

Noch einmal: Inwiefern nehme ich mit der Aussage "Der Grund: Es gibt keine andere Möglichkeit vorzugehen, als einer Variablen einen Wert zuzuweisen und dann zu schauen, wie sich das auf die anderen Variablen auswirkt" an, dass ich einen mehr als polynomiell großen Suchraum durchsuchen muss? Ich nehme das doch nicht an, sondern das will ich ja gerade beweisen.

Zitat von Christoph R.

Das stimmt nicht einmal für Fragmente von SAT die in P liegen. Z.B. ist eine fixe Input-Instanz trivialerweise in P (sie hat sogar konstante Laufzeit). Trotzdem ist z.B. { {a, b}, {-a, -b} } und { {a, -a}, {b, -b} } die Anzahl der benötigten Assignments, nach denen sich alle anderen ergeben, unterschiedlich (und hängt außerdem noch davon ab welche Werte man den Variablen gibt).

Jetzt erkläre mir, warum diese Beispiele in P liegen. Beim ersten Beispiel muss ich eine Variable setzen und habe dann alle anderen. Beim zweiten Beispiel sind es zwei Variablen, die ich setzen muss. Daher muss ich im ersten Beispiel (n choose 1) Variablen durchprobieren, bis ich die habe, die ich brauche, und im zweiten Beispiel (n choose 2). (n choose 1) ist immer gleich 1 und (n choose 2) ist, da n = 2, gleich n (n - 1) / 2, in diesem Fall also wieder 1, eine kleine Zahl, aber entscheidend ist ja die asymptotische Komplexität - diese beträgt n^n! (n^n ist nur zufälliger Weise gleich n^2! Dennoch ist die Komplexität nicht polynomiell!) Jedenfalls bestätigen deine Beispiele gerade das, was ich im Eingangsposting über die asymptotische Komplexität von k-SAT gesagt habe.

Zitat von Juggl3r

Das musst du erst einmal Beweisen, bevor du es für deinen Beweis ran nimmst. Und das zu Beweisen ist eben genau die Schwierigkeit des Problems an sich. Ich kann ja auch nicht einfach hergehen und sagen 1=2 und damit Beweis ich dann beliebiges....
Und zu Beweisen, dass es keine Möglichkeit gibt, ist schwierig. Um zu Beweisen, das es eine Möglichkeit gibt, muss ich einfach nur einen Algorithmus finden. Du hingegen musst beweisen, das es einen solchen Algorithmus nicht geben kann, was entsprechend schwieriger ist.
Sowas lernt man in Mathe 1 bzw. TIL. Daher meine Frage.

Dass es sehr viel schwieriger ist zu beweisen, dass etwas nicht geht, als dass etwas geht, weiß ich, und ich habe darüber auch Artikel in MATHEMATIQ geschrieben. [1] Ich glaube auch, dass das P-NP-Problem gerade deswegen so schwierig ist, weil wahrscheinlich P != NP gilt und das ja viel schwieriger zu beweisen, als es wäre, P == NP zu beweisen, wenn dies zutreffen würde.

Aber was diese konkrete Aussage betrifft, muss ich sagen, dass sie hieb- und stichfest ist. Wenn ich eine Lösung für SAT generieren will, muss ich zumindest eine bestimmte Anzahl von Variablen raten. Im Idealfall muss ich nur eine Variable raten und alle anderen ergeben sich daraus. Aber in jedem Fall muss ich raten.

[1] http://www.hugi.scene.org/adok/mensa/mathsig/

Zitat von Christoph R.

Weil jede _konkrete_ Instanz (eines beliebigen Problems) in P liegt, ja sogar in konstanter Zeit gelöst werden kann. Beweis: Berechne die Lösung vor, und schreib einen Algorithmus der immer genau diesen Wert zurückgibt.

Natürlich sind Algorithmen für einzelne Instanzen praktisch sinnlos, ich wollte damit nur zeigen dass deine Aussage (sinngemäß: "die Anzahl der festzulegenden Variablen, bevor der Rest daraus folgt, ist für gleich große Instanzen immer gleich") falsch ist.

Ähm... Habe ich das gesagt? Soweit ich mich erinnern kann, nein! Ich habe nur gesagt, dass es eine obere Schranke gibt, die von der Größe der Instanz abhängig ist, so dass die asymptotische Komplexität n^n beträgt, also nicht polynomiell ist.

Zitat von Christoph R.

"Wie ich erklärt habe, muss man bei Problemen, die in NP, aber nicht in P liegen, einen mehr als polynomiell großen Suchraum durchsuchen. Diese Behauptung ist nicht trivial." Richtig. Diese Behauptung ist nämlich genau die die Aussage P != NP.

Nein, wieso denn? Die Aussage P != NP ist gleichbedeutend damit, dass es Probleme gibt, die in NP, aber nicht in P liegen. Die Aussage "Man muss man bei Problemen, die in NP, aber nicht in P liegen, einen mehr als polynomiell großen Suchraum durchsuchen" sagt hingegen nichts darüber aus, ob es solche Probleme, die in NP, aber nicht in P liegen, überhaupt gibt; sie sagt also nicht aus, ob P != NP oder P == NP. Oder hast du etwas Anderes gemeint?

Zitat von Christoph R.

Und genau das war die Kritik. Wo genau es hakt, hat Juggl3r inzwischen beschrieben.

Den Einwand von Juggl3r finde ich berechtigt, nur hast du diesen Punkt meinem Verständnis nach mit deinem ersten Posting nicht angesprochen. Ansonsten, siehe meine Antwort auf Juggl3r (unmittelbar vorangehendes Posting).

Zitat von Paulchen

Im Fall, dass P == NP gilt, ist auch ein NP-vollständiges Problem mit polynomiellem Aufwand lösbar. Nimmst du nun an, für ein NP-vollständiges Problem müsstest du einen mehr als polynomiell großen Suchraum durchsuchen, kann das Ergebnis nur mehr P != NP sein, da du ansonsten einen Widerspruch hast. Der Grund für den mehr als polynomiell großen Suchraum ist aber P != NP, ansonsten hätte der Suchraum ja nur polynomielle Größe. Somit hast du bewiesen, dass P != NP genau dann gilt, wenn P != NP gilt.

Aber das nehme ich doch gar nicht an! Ich sage nur, dass ich für ein Problem, das in NP, aber nicht in P liegt, einen mehr als polynomiell großen Suchraum durchsuchen muss. (Was zu beweisen wäre, das räume ich ein.) Ich nehme aber NICHT an, dass ich für NP-vollständige Probleme einen mehr als polynomiell großen Suchraum durchsuchen muss, sondern ich ZEIGE das (beziehungsweise will ich das zeigen). Schau, wenn P == NP, dann gibt es keine Probleme, die in NP, aber nicht in P liegen - dann liegen alle Probleme, die in NP liegen, auch in P. Wenn aber P != NP, dann gibt es Probleme, die in NP, aber nicht in P liegen - und zu diesen Problemen müssen logischerweise die NP-vollständigen Probleme gehören, weil es ja innerhalb der Menge NP keine schwereren Probleme gibt als die NP-vollständigen. Deswegen kann man P != NP beweisen, indem man zeigt, dass NP-vollständige Probleme in NP, aber nicht in P liegen. Ist es jetzt klarer?

Zitat von Paulchen

Im früheren Thread habe ich erwähnt, dass ich jemanden kenne, der einen Tautologieclub gründen möchte. Ich weiß aber nicht, ob das immer noch aktuell ist. Soll ich nachfragen?

Weißt du eigentlich, dass jede wahre Aussage eine Tautologie ist?