P-NP-Problem, die Zweite

  • 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.

  • "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.

  • 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 glaube es auch nicht, aber kannst du es beweisen?
    Wie gesagt, oft ist es einfach so, dass eben das "nicht intuitve" korrekt ist, also müssen wir Beweisen, das unsere Intuition korrekt ist und es nicht einfach als gegeben annehmen.

    "The quieter you become, the more you are able to hear."
    -------------------------------------------------------------------------------------

  • Diesen Beweis liefere ich dir gerne, er ist nämlich sehr leicht

    Sorry, ich hatte in "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." den Teil "aber nicht in P liegt" überlesen. Diese Aussage stimmt dann natürlich.

    Deswegen kann man P != NP beweisen, indem man zeigt, dass NP-vollständige Probleme in NP, aber nicht in P liegen.

    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.

  • Das tolle daran ist ja, dass du annimmst, dass es einen solchen Algorithmus nicht gibt (und du damit implizit schon annimmst, dass P != NP) und damit dann beweist, dass P != NP. Deshalb hat vorher auch jemand das mit der Tautologie geschrieben ;)

    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 ;)

    "The quieter you become, the more you are able to hear."
    -------------------------------------------------------------------------------------

    Einmal editiert, zuletzt von Juggl3r (11. Oktober 2013 um 21:37)

  • 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 ;)

    Wobei das dabei wichtige Faktorisierungsproblem in seiner Entscheidungsvariante ebenfalls in NP liegt. ;)

  • Haha ;) Nein, bin ja nicht größenwahnsinnig. Zuerst einmal TripleDES und AES, asymmetrische Verschlüsselungen wie RSA usw. lösen wir dann erst übernächste Woche.... ;)

    "The quieter you become, the more you are able to hear."
    -------------------------------------------------------------------------------------

  • 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?

  • 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.

  • 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 gibt ueberabzaehlbar viele Funktionen [tex='f : \mathbb{N} \rightarrow \{0,1\}'][/tex]

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

  • 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?

    Einmal editiert, zuletzt von Adok (12. Oktober 2013 um 16:36)

  • Angenommen es gaebe nur abzaehlbar viele solche Funktionen. Nennen wir die Menge dieser Funktionen A und die Bijektion von A nach [tex='\mathbb{N}'][/tex]

    nennen wir h. Wir konstruieren nun eine Funktion g von den nat. Zahlen nach {0,1}, welche nicht in A liegen kann.

    g(n) = 1 falls h(n)[n] = 0
    = 0 sonst.

    Angenommen es gibt ein m, sodass h(m) = g. Schauen wir uns dann g(m) an:

    Fall 1: g(m) = 1. Dann ist aber h(m)[m] = 0, somit gilt g != h(m)
    Fall 2: g(m) = 0. Dann gilt h(m)[m] = 1, somit gilt g != h(m)

    Das ist nur der Satz von Cantor in 0-1 Folgen ausgedrueckt. Das selbe kannst mit der Potenzmenge machen.


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

    Tut mir Leid, dazu bist du zu spät dran, das gibt es schon ;)
    Nennt sich One-Time-Pad und man kann Beweisen, dass dieser Algorithmus 100%tige Sicherheit bietet.

    Weiters kann man beweisen, dass eine Verschlüsselung nur 100%tige Sicherheit bietet, wenn der Schlüsseltextraum größer oder gleich dem Klartextraum ist, so wie bei One-Time-Pad. Solche Algorithmen sind aber unpraktibael.

    "The quieter you become, the more you are able to hear."
    -------------------------------------------------------------------------------------

    Einmal editiert, zuletzt von Juggl3r (13. Oktober 2013 um 15:19)

  • Wenn das wer schaft, stürzt sich Adok von der nächsten Brücke.....

    "The quieter you become, the more you are able to hear."
    -------------------------------------------------------------------------------------

    Einmal editiert, zuletzt von Juggl3r (13. Oktober 2013 um 23:04)

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!