Wenn

10

Wenn P=NP , ist dann L=NL ? Ich stelle diese Frage, weil für andere nicht deterministische Klassen P=NP anscheinend immer feststellt, dass sie ihren deterministischen Gegenstücken gleich sind.

ttr
quelle

Antworten:

15

Dies ist eine offene Forschungsfrage. Nach unserem derzeitigen Kenntnisstand würde das Wissen um weder L = N L noch LN L bedeuten . Und umgekehrt würde das Wissen um L = N L oder LN L nichts über die Frage P vs N P bedeuten . (Aber es ist möglich, dass der Beweis von L gegen N L etwas über P gegen N P aussagtP=NPL=NLLNLL=NLLNLPNPLNLPNP oder umgekehrt.)

Wir kennen , wobei die Gleichheit aus dem Satz von Savitch folgt . Die nichtdeterministische Version des Raumhierarchiesatzes besagt, dass N LN P S P A C E.LNLPNPPSPACE=NPSPACENLNPSPACENLPSPACE

David Richerby
quelle