Was genau bedeuted P = NP?

In P sind alle Berechnungsprobleme, die in Polynomialzeit auf einer deterministischen Turing Maschine gelöst werden können. Beispielsweise "Ist folgendes Array bereits sortiert?"

In NP sind alle Berechnungsprobleme, die in Polynomialzeit auf einer nichtdeterministischen Turing Maschine gelöst werden können. Beispielsweise "Wie lauter die Primfaktorenzerlegung folgender Zahl?"

Wenn P=NP ist, dann gibt es für Probleme wie der Primfaktorenzerlegung oder SAT einen effizienten Algorithmus.

Suppose A is NP-hard and B is NP-complete. If B is in P then A is in P? Warum stimmt das nicht?

Das ein Problem A NP-schwer ist, bedeutet nicht, dass A auch in NP liegt. Es bedeutet, dass A auf alle Probleme in NP reduziert werden kann. Diese Eigenschaft erfüllen beispielsweise auch ExpTime-vollständige Probleme.

Vielleicht hilft dir folgende Analogie: Es sei a eine reelle Zahl und M eine Teilmenge der reellen Zahlen. Wir sagen a ist eine obere Schranke von M, wenn alle Elemente in M kleiner oder gleich a sind. Beispielsweise M=[0;4]. Dann sind die Zahlen a=9, a=4 und a=695550 alles obere Schranken.

Ein Problem ist NP-schwer würde ähnlich zu diesen oberen Schranken funktionieren. Es darf auch deutlich oberhalb von NP liegen, aber es muss mindestens so schwer sein, wie die schwersten Probleme in NP. NP-vollständig verlangt zusätzlich zur NP-schwere, dass es auch in NP liegt. In der Analogie erfüllt nur die 4 die Eigenschaft in M zu liegen und gleichzeitig eine obere Schranke von M zu sein.

A is regular and A <=m B -> B is regular Warum stimmt das nicht?

Ich verstehe nicht, was hier steht.

A is in P and B is in P => A concat B is in P? Warum stimmt das ebenfalls nicht?

Das diese Implikation nicht gelten solle, überrascht mich auch. Ich mache dazu einmal einen formalen Beweis:

Idee: Wir raten wo das zweite Wort beginnt. Hier ein polynomialzeitbeschränkter Pseudocode.

function bool check(a,b) where 
    if( checkA(a) && checkB(b) )
        return true;
    else if(b == lambda)
        return false;   // Wenn b bereits das leere Wort ist, dann gebe false aus.
    else{
        x ++ b' := b // wir entfernen das erste Zeichen aus b. Der neue String heißt b'. Das entfernte Zeichen heißt x
        a' := a ++ x // wir fügen x ans Ende von a an.
        return check(a',b') // rekursiver Schritt.
    }

checkA(a) soll die Funktion sein, die überprüft, ob das Wort a in A liegt. Diese Funktion liefert in Polynomialzeit einen Boolean zurück. Analog für checkB(b). Meine Behauptung ist, dass check(lambda, w) zurück gibt, ob w in A concat B liegt.

Korrektheit:

Zunächst muss man sich überlegen, warum dieser Code tatsächlich korrekt arbeitet.

Falls w = x ++ y mit x in A und y in B, dann sind die Codevariablen a und b im (length(x)+1)-ten Rekursionsschritt identisch definiert wie x und y (Beweis per Induktion). Dementsprechend liefert checkA(a) && checkB(b) ein true und der Code terminiert.

Umgekehrt, wenn w nicht aufgeteilt werden kann in x ++ y, dann liefert checkA(a) && checkB(b) niemals true. b verliert in jedem Rekursionsschritt einen Buchstaben und wird somit irgendwann leer sein, sodass b == lambda erfüllt ist. Der Code terminiert korrekterweise mit einem false.

Der Code arbeitet also korrekt. Aber arbeitet er auch schnell genug um in P zu liegen?

Zeitbeschränkung

1. Die Zeilen "b==lambda", "x ++ b' := b" oder "a' := a ++ x" sind trivialerweise in Polynomialzeit berechnet.
2. In jedem Schritt verliert b ein Zeichen, bis es leer wird. Es gibt also höchstens length(w)+1 viele Rekursionsschritte. Dies ist polynomiell beschränkt.
3. Der Aufruf checkA(a) ist in Polynomialzeit berechenbar, denn A ist in P. Das Wort a ist polynomiell beschränkt, denn es ist in jedem Rekursionsschritt kleiner oder gleich dem Startwort w. Analoge Argumentation für b.

Somit habe ich einen formalen Beweis dafür, dass A concat B in P liegt, wenn A und B in P liegen. Die Implikation gilt also.

Auch Wikipedia sagt aus, dass Sprachen abgeschlossen unter Konkatenation sind "Languages in P are also closed under reversal, intersection, union, concatenation, Kleene closure, inverse homomorphism, and complementation." https://en.wikipedia.org/wiki/P_(complexity)

Liebe Grüße

cunni