Was ist falsch an diesem bedingten Beweis von P = NP?

8

Ich habe mir kürzlich den folgenden Beweis ausgedacht, dass L = P P = NP impliziert.

Angenommen, L = P. Sei A ein Problem in NP. Nach der Verifiziererdefinition von NP hat jede positive Lösung für A einen Zeugen, der in Polynomzeit verifiziert werden kann. Da P = L ist, kann dieselbe Lösung im logarithmischen Raum verifiziert werden. Somit ist NP = NL. Aber dann ist NL in P enthalten, was bedeutet, dass NP in P enthalten ist und daher P = NP.

Aufgrund der Hypothese eines effizienten Marktes vermute ich, dass dieser Beweis fehlerhaft ist. Ich kann jedoch die genaue Art des Fehlers nicht bestimmen. Kann jemand darauf hinweisen?

user44898
quelle

Antworten:

9

Angenommen, L = P. Sei A ein Problem in NP. Nach der Verifiziererdefinition von NP hat jede positive Lösung für A einen Zeugen, der in Polynomzeit verifiziert werden kann. Da P = L ist, kann dieselbe Lösung im logarithmischen Raum verifiziert werden. Somit ist NP = NL.

Sie haben diesen NP nicht gezeigt=xAyy

1

David Richerby
quelle