Warum können wir die Antwort eines NDTM nicht effizient umdrehen?

Ich habe mehrmals gelesen, dass es nicht möglich ist, die Antwort eines NDTM effizient umzudrehen. Ich verstehe jedoch nicht warum. Bei einem NDTM , das in O ( n ) ausgeführt wird , heißt es in diesem Text (Abschnitt 3.3) beispielsweise, dass unklar ist, wie ein anderes NDTM T in Zeit bestimmen kann, wie die Antwort von umgedreht werden soll.$M$$O(n)$$T$$O(n^{100})$$M$

Mein Problem ist wie folgt: Ein NDTM gibt wenn eine Folge nicht deterministischer Entscheidungen existiert, die zum akzeptierenden Zustand führt. Darüber hinaus gibt es eine universelle NDTM- , die jedes NDTM mit nur geringem (logarithmischem) Overhead simulieren kann. Warum können wir T also nicht wie folgt konstruieren: Simulieren Sie zuerst M mit dem universellen NDTM, das in der Zeit . Geben Sie dann 1 - Ms Antwort aus. Dies würde bedeuten, dass wir die Antwort eines beliebigen linearen NDTM in der Zeit umdrehen können .N U O ( n log n ) O ( n log n $1$$NU$$O(n\log n)$$O(n\log n)$

Eine nicht deterministische Turing-Maschine akzeptiert, wenn mindestens ein Pfad akzeptiert; Es wird nur abgelehnt, wenn alle Pfade ablehnen. Diese Asymmetrie macht es schwierig, "Antworten umzudrehen".

Angenommen, Sie haben eine nicht deterministische Turing-Maschine  , die zwei Pfade für die Eingabe  : einer akzeptiert, der andere lehnt ab.  hat mindestens einen Akzeptanzpfad für  , also akzeptiert es. Angenommen, wir möchten eine Maschine produzieren, die genau die Eingaben akzeptiert, die  ablehnt. Der offensichtliche erste Versuch besteht darin, zu nehmen  und seine akzeptierenden Zustände abzulehnen und seine ablehnenden Zustände zu akzeptieren.  hat einen Akzeptanzpfad für  und einen Ablehnungspfad; Diese neue Maschine  hat einen Ablehnungspfad und einen Akzeptanzpfad. Also akzeptiert es immer noch  , was es ablehnen sollte!w M w M M M w M '$M$$w$$M$$w$$M$$M$$M$$w$$M'$$w$

Eine nichtdeterministische Maschine kann nicht alle Pfade gleichzeitig betrachten und basierend auf den Aktionen all dieser Pfade Maßnahmen ergreifen. Wenn Sie möchten, können Sie sich das als eine Form der Parallelität vorstellen, bei der es den Threads verboten ist, miteinander zu kommunizieren. Wenn alle Threads beendet sind, muss sich das Programm die folgende Frage stellen: "Hat mindestens einer meiner Threads akzeptiert?" Wenn die Antwort ja ist, ist es gesetzlich verpflichtet zu akzeptieren; Wenn die Antwort Nein lautet, ist sie gesetzlich zur Ablehnung verpflichtet. Es kann nichts anderes tun.

Wenn Sie eine nichtdeterministische Maschine  mit einer anderen, , simulieren simuliert jeder Pfad von  einen Pfad von  und sieht nur diesen Pfad. Es kann nicht sagen: "Wenn all diese anderen Pfade abgelehnt werden, werde ich akzeptieren", weil es die anderen Pfade nicht sehen kann. es kann nur sich selbst sehen. Alles, was es möglicherweise sagen könnte, sind Dinge wie "Wenn der von mir simulierte Pfad akzeptiert wird, werde ich ablehnen" oder "Wenn der von mir simulierte Pfad akzeptiert wird, werde ich auch akzeptieren". Am Ende der Berechnung muss die Maschine dann sagen: "Wenn einer meiner Pfade akzeptiert wird, akzeptiere ich auch", was zu dem oben beschriebenen Problem führt. Um das Verhalten von , wird jeder Pfad vonM ' M ' M M M ' M $M$$M'$$M'$$M$$M$$M'$muss sagen: "Wenn der von mir simulierte Pfad akzeptiert wird, lehne ich ab; sonst akzeptiere ich" und am Ende der Berechnung muss die Maschine sagen: "Wenn alle meine Pfade akzeptiert werden, akzeptiere ich; ansonsten lehne ich ab . " Dies liegt daran, dass, wenn alle Pfade des Simulators akzeptiert wurden, dies bedeutet, dass alle Pfade von abgelehnt wurden, also abgelehnt wurde, sodass der Simulator akzeptieren muss. Der Simulator ist jedoch keine gültige nichtdeterministische Turing-Maschine, da er nicht das gesetzlich vorgeschriebene Akzeptanzkriterium verwendet. Das kann es nicht.$M$$M$

Der einzige Weg, um herauszufinden, ob eine nicht deterministische Maschine ihre Eingabe ablehnt, besteht darin, jeden möglichen Pfad auszuprobieren und zu überprüfen, ob sie alle ablehnen. Wenn sogar einer von ihnen akzeptiert würde, würde die Maschine die Eingabe akzeptieren. Aber jeden möglichen Weg auszuprobieren ist exponentiell langsamer als nur einen.

$O(n)$$O(n)$

$NU$$O(n log( n))$$n log (n)$$M$$M$

$\stackrel{?}{=}$$\stackrel{?}{=}$