Ich bin nicht sicher, wie man überhaupt anfängt. Meine Idee ist es Poly-Zeit-Reduktion von einigen NP - Complete Problem zu bieten. E_tmWie kann man beweisen, dass E_tm = {M | M ist eine Turingmaschine, die nichts akzeptiert} ist NP-Hard?
Was ich nicht verstehe ist, dass, wissend, dass E_tm nicht entscheidbar ist, aber NP-Harte Klasse entscheidbar ist.
Lösung:
DF: Ein Problem ist NP-schwer, wenn alle Probleme in NP sind Polynomzeit reduzierbar auf sie, auch kann thoughit nicht in NP selbst sein (P326 Sipser) (die einzige Definition unser Buch hat) . Für jede Sprache L ', die in NP ist, wenn wir zeigen, dass wir die Polyzeit auf Etm reduzieren können. Dies wird beweisen, dass Etm NP - schwer ist. Da L 'in NP per definitionem existiert gibt es ein TM (NTM aber da sie äquivalent in der Macht sind, schreibe ich TM) M' so dass entscheidet L '.
TM M'' that takes as an input <M,w> constructs
TM M' such that
on arbitrary x
if w = x
run M on w if accept => reject
if reject => accept
else reject.
Daher akzeptiert M w w, wenn M '' alle Eingaben ablehnt. Lassen Sie uns das bestätigen. Nehmen wir zuerst an, dass M w annimmt, dann M '' auf irgendeine Eingabe zurückweist, daher L (M '') = leer. Nehmen wir nun an, dass M w ablehnt, dann M '' akzeptiert, daher ist L (M '') nicht leer. Beachten Sie, dass die Konstruktion des M '' Polynomzeit benötigt. Das vervollständigt den Beweis.