P-NP-Problem, die Zweite

Zitat von Juggl3r

Hm, in meinen Augen gibts 2 Möglichkeiten:
a) Du verstehst das grundlegende Problem nicht
oder
b) Du bist viel intelligenter als ich und ich kann deiner Argumentation nicht folgen. (in diesem Fall möchte ich mich höfflichst bei dir Entschuldigen!)

Beispiel: Ich behaupte jetzt einfach mal es gibt einen Algorithmus G welcher als Eingabe eine beliebige Formal aus k-SAT nimmt und als Ausgabe die Lösung der Formel liefert. Der Algorithmus "rät" nicht die richtige Lösung, sondern nimmt die Klauseln her und wendet die Operation xi darauf an, wobei die Operation xi noch nicht erfunden/gefunden sein muss (es reicht, das es sie gibt, wann und ob überhaupt wir Menschen sie finden, ist egal).

Deine Aufgabe ist jetzt zu Beweisen, das es einen solchen Algorithmus G nicht geben kann, denn dann hättest du diese Aussage untermauert und könntest sie hernehmen für einen Beweis für P != NP

Du meinst, dass man auf die gesamte aussagenlogische Formel F eine Funktion f anwenden kann, welche die korrekte Variablenbelegung zurückliefert. Gegeben Formel F, ich benutze f(F) und bekomme v1 = ..., v2 = ... usw.

Wenn es eine solche Funktion gibt und die Komplexität asymptotisch kleiner als n^n ist, dann ist die Konsequenz, dass k-SAT eine geringere Komplexität als n^n hat.

Ich verstehe schon, was du meinst, und ich gebe dir Recht, dass es logisch unzulässig ist zu sagen, nur weil man keinen anderen Algorithmus kennt, dass es keinen geben könnte. Du musst aber bedenken, dass eine mathematische Funktion eine SAT-Formel höchstens verarbeiten könnte, wenn diese SAT-Formel als Zahl kodiert vorläge. Die Kodierung würde nicht ins Gewicht fallen, eine SAT-Formel könnte locker in linearer Zeit in eine Zahl umgewandelt werden. Aber ich glaube nicht, dass man durch eine billige Operation wie "modulo 2" überprüfen kann, ob eine so kodierte aussagenlogische Formel erfüllbar ist. Ich gebe dir nur Recht, dass jeder Algorithmus als mathematische Funktion ausgedrückt werden kann (das ist ja das Prinzip der funktionalen Programmierung). Nur finde ich nicht, dass wir uns auf diese Ebene einlassen müssen, weil ja auch umgekehrt jede mathematische Funktion als Algorithmus ausgedrückt werden kann. Es genügt also, das Problem auf der Ebene der Algorithmen zu analysieren.

Das Problem SAT ist übrigens gleichbedeutend damit, eine Gleichung zu lösen, in der die Variablen nur die Werte 0 oder 1 annehmen können. Jede Instanz von SAT kann in ein solches Problem umgewandelt werden. Vielleicht könnte uns das Nachdenken hierüber auf neue Ideen bringen.

Zitat von Christoph R.

"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.)" Dann liefere diesen Beweis bitte. Genau dieser fehlt nämlich. Und das führt uns zurück zur ursprünglichen Frage ob P != NP.

Diesen Beweis liefere ich dir gerne, er ist nämlich sehr leicht: Wenn ich nur einen polynomiell großen Suchraum durchsuchen muss und die Lösung in polynomieller Zeit überprüft werden kann, dann ist das Problem in P. Diese Aussage ist logisch äquivalent zu der Aussage: Wenn ein Problem nicht in P ist, dann muss ich einen größeren als polynomiellen Suchraum durchsuchen oder die Lösung kann nicht in polynomieller Zeit überprüft werden. Per definitionem kann die Lösung eines Problems, das in NP ist, in polynomieller Zeit überprüft werden. Daraus folgt, dass ich bei einem Problem, das in NP, aber nicht in P ist, einen größeren als polynomiellen Suchraum durchsuchen muss (die Lösung kann aber in polynomieller Zeit überprüft werden).

Zumindest das wäre also bewiesen.

Zitat von Christoph R.

Diese Aussage stimmt und ist gut bekannt. Würdest du zeigen, dass k-SAT nicht in P liegt, dann würde daraus P != NP folgen.

Jedoch hast du das bis jetzt nicht gezeigt. Die Lücke im Beweis ist die Behauptung: "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.". Das hast du nach wie vor nicht bewiesen, ist aber genau der Kern des Problems. Die restlichen Schlussfolgerungen deines Beweises mögen ja durchaus richtig sein, bringen das Problem aber nur in eine leicht andere Form.

Einverstanden!

OK, es sieht so aus, als hättet ihr zwei verstanden, was ich gemeint habe und worin die Lücke in meinem Beweis-Versuch besteht. Ich finde, man sollte sich schon Gedanken darüber machen, ob es irgendwie möglich ist zu zeigen, dass man SAT nicht anders lösen kann als, indem man einer bestimmten Anzahl von Variablen einen Wert zuweist und sich dann die Werte der übrigen Variablen ergeben. In diesem Zusammenhang möchte ich vorschlagen, vielleicht gar nicht über SAT zu diskutieren, sondern über ein anderes, anschaulicheres Problem:

Gegeben ist eine Konstante c. Gesucht sind n natürliche Zahlen ungleich 1 (denn 1 ist das neutrale Element der Multiplikation, was das Problem trivial machen würde), die miteinander multipliziert diese Konstante c ergeben.

Dieses Problem scheint mir genauso komplex wie SAT zu sein, es scheint mir aber einfacher zu analysieren zu sein. Ich wüsste für dieses Problem auch keine andere Möglichkeit, als nach einem Algorithmus vorzugehen, der für n - 1 Variablen die Werte durchiteriert, wobei sich der Wert der n-ten Zahl ergeben würde. Vielleicht könnte man für dieses Problem leichter als für SAT zeigen, dass es gar nicht anders gelöst werden kann. Vorschläge dazu?

Zitat von Juggl3r

Vorschlag: Du verwirfst die Idee mit dem P vs. NP Problem und stattdessen versuchen wir eine moderne Verschlüsselung zu knacken, da muss man genauso viel logisch denken können und das hat meiner Meinung nach eine viel höhere Erfolgschance und da würde ich sogar mitmachen

Hmm. Soweit ich weiß, wären wir zumindest nicht die Ersten in der Welt, denen das gelingen würde (falls es uns gelingen sollte) - in dieser Beziehung hätte die NSA uns etwas voraus.

Noch interessanter fände ich die Aufgabe, eine Verschlüsselung zu entwickeln, die niemand knacken kann.

Zitat von _gerald_

Es gibt ueberabzaehlbar viele Funktionen

[tex='f : \mathbb{N} \rightarrow \{0,1\}'][/tex]

, jedoch bei den (in der Komplexitaetstheorie betrachteten) Maschinenmodellen nur abzaehlbar viele Algorithmen...

Bitte um nähere Erläuterung oder Literatur-Referenz. (Ich glaube schon zu verstehen, was du meinst, aber ich kann es nicht ganz nachvollziehen.)

Edit: Ich nehme an, du meinst, es gebe überabzählbar viele Funktionen, weil es auch Funktionen gibt, die eine Zahl mit unendlich vielen Nachkommastellen zurückliefern?