Wie kann gezeigt werden, dass die Gruppe von Maschinen, die Sprachen in akzeptieren , nur dann entscheidbar ist, wenn ?

8

Ich möchte Ihre Hilfe beim Nachweis, dass die Sprache ist entscheidbar, wenn .

L={M|L(M)NPP}
P=NP

Wenn , ich, dass es die Sprache leerer Turing-Maschinen ist. So ist ein Problem - aber das ist nicht das, was gefragt wird ist, so habe ich verwirrt.P=NPLco-RE

Ich weiß, dass ich, um anzuzeigen, ein Problem muss, bei dem es sich ebenfalls um und .P=NPNPCP

Irgendeine Hilfe? Vielen Dank!

Jozef
quelle

Antworten:

9

Es sind zwei Fälle zu berücksichtigen.

  1. Angenommen, . Dann ist . Die leere Sprache ist entscheidbar; Da kein Wort dazu gehört, ist es trivial zu entscheiden, ob ein Wort dazu gehört oder nicht.P=NPL={ML(M)}=

  2. Angenommen, . Ihr Ergebnis folgt nun direkt aus dem Satz von Rice .PNP

Dave Clarke
quelle