Kann festgestellt werden, ob die Sprache L in NP liegt?

15

Ist es möglich, bei einer von einer Turing-Maschine definierten Sprache L algorithmisch zu bestimmen, ob L in NP liegt?

txwikinger
quelle
Zurück zur Komplexitätstheorie. Nicht sicher, was dies mit NP-Vollständigkeit zu tun hat.
Aryabhata
1
FWIW, trotz der Abstimmungen auf der Vorschlagsseite, denke ich, dass diese Frage umfassender ist als die Frage zum Factoring, da die Frage zum Factoring in den meisten Kursen zur Einführung in Komplexität behandelt wird, aber diese Frage wird in vielen Kursen für Hochschulabsolventen nicht einmal behandelt Komplexitätskurse.
Joshua Grochow
1
Wird dies nicht in Einführungskursen über Berechenbarkeit als typische Anwendung von Rices Theorem behandelt?
Moritz
3
Moritz - obwohl die Ja / Nein-Antwort auf diese Frage durch Rices Theorem abgedeckt ist, finden Sie in meiner Antwort unten weitere interessante Ergebnisse. Vielleicht solltest du, txwikinger, die Frage auf "Wie komplex ist die Menge {i: L (M_i) in NP}?" Ändern?
Joshua Grochow
Ich werde die Antwort von Joshua hier unterstützen. Die Antwort mag offensichtlich sein, wenn die Sprache von einer Turing-Maschine angegeben wird, aber die Antwort ist dieselbe (und vielleicht nicht ganz so offensichtlich), wenn wir zulassen, dass die Sprache in einem beliebigen Format angegeben wird.
Anand Kulkarni

Antworten:

24

Nein. Erstens ist dies nach dem Satz von Rice eine Eigenschaft von TMs, die nur von der Sprache abhängt, die sie berechnen, und daher nicht berechenbar ist.

Darüber hinaus ist jedoch bekannt, dass die Indexmenge von (dh die Menge von TMs, die Sprachen in berechnen ) vollständig ist ( in der arithmetischen Hierarchie der , nicht die Polynom-Hierarchie).N P 0 30 3NPNPΣ30Σ30

Fragen wie diese wurden zuerst von Hajek untersucht . Weitere Informationen finden Sie zB in diesem Artikel von Ken Regan.

Noch ein paar großartige Nuggets aus Hajeks Papier:

  • Die Indexmenge vonP ist -komplett.Σ30
  • ist Π 0 2 -vollständig{i:PL(Mi)NPL(Mi)}Π20
  • Es gibt eine Gesamt-Turing-Maschine (hält an allen Eingaben an) so dass P L i = N P L i, aber die Aussage " P L i = N P L i " unabhängig ist (wobei L i = L ( M i ) ) . Ähnliches gilt für Relativierungen wo P N P .MiPLi=NPLiPLi=NPLiLi=L(Mi)PNP
Joshua Grochow
quelle
1
Hier scheint die Frage ein Versprechensentscheidungsproblem zu sein (es wird versprochen, dass die gegebene Sprache von einem TM entschieden wird und nicht nur anerkannt wird), im Gegensatz zu einem Gesamtentscheidungsproblem. Wird dann der Satz von Rice hier noch anwendbar sein? Erinnern wir uns daran, dass der Beweis des Satzes von Rice die Unentscheidbarkeit des Anhaltens beinhaltet, daher ist Unentscheidbarkeit dort von wesentlicher Bedeutung.
Zeyu
2
In der gestellten Frage wurde die Sprache L "von einer Maschine vorgegeben, die darüber entscheidet". Es war also wirklich so: Wenn eine Turing-Maschine M gegeben ist, kann bestimmt werden, ob L (M) in NP ist. Wenn die Sprache L nicht durch ein TM spezifiziert wäre, sondern nur als Teilmenge der natürlichen Zahlen angegeben würde, was würde es bedeuten, algorithmisch zu entscheiden, ob L in NP ist? Wie können wir uns insbesondere vorstellen, dass L in einen Algorithmus eingegeben wird, wenn L selbst nicht durch eine endliche Beschreibung gegeben ist?
Joshua Grochow
1
Ja, ich weiß. In Rices Theorem ist es jedoch möglich, dass das TM keine Sprache bestimmt, dh keine Gesamtfunktion berechnet.
Zeyu
2
Es ist eine allgemeine Heuristik, dass man angesichts einer semantischen Eigenschaft von Turing-Maschinen wie "M definiert eine NP-Sprache" zunächst versuchen sollte, diese Eigenschaft in Logik erster Ordnung auszudrücken. Dadurch wird die Eigenschaft auf eine Ebene der arithmetischen Hierarchie gesetzt. Die Heuristik ist, dass die Eigenschaft normalerweise für diese Hierarchieebene vollständig ist. Ich möchte fragen, ob es zu dieser Heuristik bemerkenswerte Gegenbeispiele gibt.
Andy Drucker
2
Skaliert man auf die Polynomialhierarchie, ist es weniger wahrscheinlich, dass sich die Dinge so gut verhalten. Betrachten Sie beispielsweise die Eigenschaft "C ist eine boolesche Schaltung mit minimaler Größe (für die berechnete Funktion)". Dieses Problem ist NP-schwer und kann in die Polynomialhierarchie aufgenommen werden, es ist jedoch offen, ob es für die Ebene, in der es sich natürlich befindet, vollständig ist. (Solche Ergebnisse sind für einige eingeschränkte Schaltkreisklassen, z. B. DNFs, bekannt; siehe die zweiteilige Umfrage "Vollständigkeit in der Polynom-Hierarchie" von Schaefer und Umans.)
Andy Drucker
5

Die Antwort auf Ihre Frage lautet Nein, wie Joshua Grochow betonte.

Es ist jedoch, wie Holger feststellte, möglich, in linearer Zeit zu prüfen, ob die nicht deterministische Turing - Maschine (NTM) sich selbst "taktet" und nach n ^ k Schritten für eine Konstante k anhält, und zwar durch eine Standardmethode zum Simulieren einer Uhr (wie z. B. die Turing - Maschine) Code unten). Oft, wenn eine Zeitung oder ein Buch (fälschlicherweise) andeutet, dass es möglich ist, festzustellen, ob eine NTM eine Polynomzeit ist, ist dies das, was sie wirklich bedeuten. Vielleicht haben Sie deshalb die Frage gestellt? (Ich hatte die gleiche Frage, als ich zum ersten Mal die Komplexitätstheorie lernte und irgendwo die Aussage sah, dass es möglich ist, zu überprüfen, ob ein TM poly-time ist.) Die eigentliche Frage ist, warum man dies tun möchte, worauf ich im Folgenden näher eingehen werde wie .

Es gibt viele Möglichkeiten, eine solche Uhrfunktion hinzuzufügen. Stellen Sie sich zum Beispiel vor, Sie führen am Eingang x der Länge n abwechselnd eine Anweisung des "primären Algorithmus" aus, der getaktet wird, und dann eine Anweisung des folgenden Algorithmus, der in (etwas in der Nähe von) n ^ k Schritten endet:

für i_1 = 1 bis n
  für i_2 = 1 bis n
...
        für i_k = 1 bis n
          no-op;
Rückkehr;

Wenn der obige Code zurückgegeben wird, bevor der primäre Algorithmus anhält, halten Sie die gesamte Berechnung an (z. B. mit Zurückweisung).

Der Algorithmus, der entscheidet, ob ein NTM von dieser Form ist, meldet, wenn er als Versuch interpretiert wird, anhand eines Algorithmus zu entscheiden, ob seine Eingabe ein Mehrfachzeit-NTM ist, einige falsche Negative: Einige NTMs werden garantiert in der Polynomzeit angehalten, obwohl Sie führen nicht abwechselnd eine Anweisung eines Algorithmus mit einer Anweisung einer Uhr aus, wie der obige Code (daher würde sie abgelehnt, obwohl sie poly-time ist).

Es gibt aber keine Fehlalarme. Wenn ein NTM den Test besteht, stoppt es definitiv in der Polynomzeit, daher definiert es eine NP-Sprache. Möglicherweise wird jedoch das Verhalten des zugrunde liegenden primären Algorithmus geändert, wenn die Uhr manchmal abläuft, bevor der primäre Algorithmus anhält, wodurch die Berechnung zurückgewiesen wird, obwohl der primäre Algorithmus möglicherweise zugestimmt hat, wenn genügend Zeit zum Beenden zur Verfügung steht. Daher kann die gewählte Sprache von der des primären Algorithmus abweichen. Aber, und dies ist der Schlüssel, wenn der ausgeführte primäre Algorithmus tatsächlich ein Polynom-Zeit-Algorithmus ist, der in der Zeit p (n) abläuft, und wenn die Konstante k in der Uhr groß genug ist, dass n ^ k> p (n), dann Der primäre Algorithmus stoppt immer, bevor die Uhr abläuft. In diesem Fall wird die Antwort des primären Algorithmus nicht geändert, so dass der primäre Algorithmus und das getaktete NTM, das ihn simuliert, dieselbe NP-Sprache bestimmen.

Warum ist das wichtig? Dies bedeutet, dass es möglich ist, "alle NP-Sprachen aufzuzählen" (was, wie ich bereits sagte, in der Literatur oft als "Entscheidung darüber, ob eine gegebene NTM eine Mehrfachzeit ist" oder "alle Mehrfachzeit-NTMs aufzuzählen" angegeben ist). Genauer gesagt ist es möglich, eine unendliche Liste von M_1 M_2, ... von NTM mit den folgenden Eigenschaften aufzulisten

  1. Jedes M_k läuft in Polynomialzeit (zum Beispiel durch Anhängen einer ^ k-Zeituhr an M_k) und entscheidet somit über eine NP-Sprache
  2. Jede NP-Sprache ist die Sprache, die von einem M_i in der Liste festgelegt wird.

Was nicht passiert ist, dass jedes polynomielle NTM auf der Liste steht. Aber jede NP-Sprache hat eine unendliche Anzahl von NTMs, die sie darstellen. Somit ist garantiert, dass jede NP-Sprache mindestens einige ihrer repräsentativen NTMs auf der Liste hat, insbesondere alle diese NTMs mit einem ausreichend großen Index k, dass n ^ k die Laufzeit von M_k überschreitet.

Dies ist nützlich, um Tricks wie die Diagonalisierung auszuführen, die die algorithmische Aufzählung solcher unendlichen (oder unbegrenzten) Listen aller NP-Sprachen erfordern. Und natürlich gilt diese ganze Diskussion für viele andere Arten von Maschinen außer für Mehrfachzeit-NTMs, wie zum Beispiel für Mehrfachzeit-deterministische TMs.

Dave Doty
quelle
3

p(n)

Holger
quelle
2
Das funktioniert nur, wenn es sich um ein getaktetes nicht deterministisches TM handelt. Wenn ich Ihnen nur ein getaktetes TM gebe (sogar eines, das in exponentieller Zeit abläuft), ist es immer noch unentscheidbar, ob die Sprache, für die es sich entscheidet, in NP ist oder nicht. Wenn jedoch N_1, N_2, ... eine Aufzählung von TMs mit Exponentialuhren ist, ist die Menge {i: L (N_i) in NP} wahrscheinlich nicht mehr Sigma_3-vollständig, da Sie bereits garantiert sind, dass die N_i sind total, aber es ist sicher noch nicht berechenbar.
Joshua Grochow