Könnte eine beschreibende Komplexitätsversion von Rices Theorem verwendet werden, um AC0 und PSPACE zu trennen?

In dieser Frage wurde erwähnt, dass es beschreibende Komplexitätsversionen des Satzes von Rice gibt. Ich habe einen Beweis für den folgenden Satz gefunden:

Bei einer Komplexitätsklasse C können nichttriviale Eigenschaften von Sprachen in C nicht in C berechnet werden

Ich hatte zuvor den gefundenen Beweis veröffentlicht, aber weil er so lang war und in den Kommentaren darauf hingewiesen wurde, dass dieses Papier bereits einen Beweis für diesen Satz enthält, habe ich ihn entfernt. (Wenn Sie aus irgendeinem Grund unbedingt meinen Beweis sehen möchten, lesen Sie bitte die vorherigen Überarbeitungen dieser Frage.)

Mein Interesse ist, ob dieser Satz verwendet werden könnte, um AC0 und PSPACE zu trennen. Hier ist das Argument:

Betrachten Sie die Eigenschaft P der Komplexitätsklasse AC0, die wie folgt definiert ist:

P : Die Eigenschaft, eine FO-Abfrage zu sein, die eine bestimmte feste Struktur akzeptiert, nämlich die Struktur, die aus einem Element, keinen Funktionen, keinen Konstanten und keinen Beziehungen besteht

Nach dem obigen Theorem ist P in AC0 eindeutig nicht entscheidbar; Es ist eine nicht triviale Eigenschaft von FO-Abfragen.

Eine kleine Untersuchung sollte jedoch zeigen, dass die Berechnung, ob eine FO-Abfrage eine so einfache Struktur akzeptiert oder nicht, genauso einfach wie TQBF entschieden werden kann. somit ist P in PSPACE entscheidbar.

Um Klarheit in diesem Punkt zu gewährleisten (dass P in PSPACE berechenbar ist): Beachten Sie, dass für die Eigenschaft, an der wir interessiert sind, die Struktur FO sein muss. Wir versuchen also festzustellen, ob eine FO-Abfrage, die auf einer Einzelelementstruktur ohne Beziehungen ausgeführt wird, akzeptiert wird. Da es keine zu behandelnden Beziehungen gibt, sollte klar sein, dass die Entscheidung über eine solche FO-Abfrage der Entscheidung über eine Instanz von TQBF entspricht. Da es keine Beziehungen gibt, besteht die einzige Herausforderung darin, zu bewerten, ob die quantifizierte Boolesche Formel wahr ist oder nicht. Dies ist im Grunde nur TQBF, daher ist P in PSPACE berechenbar.

Da P in PSPACE berechenbar ist, aber nicht in AC0, sollten wir schließen können, dass AC0! = PSPACE. Ist diese Argumentation richtig oder habe ich irgendwo einen Fehler gemacht? Ich bin besonders besorgt über den vorhergehenden Absatz; Ich werde versuchen, das Argument morgen zu klären und zu aktualisieren, nachdem ich die Gelegenheit habe, etwas mehr über die Darstellung nachzudenken.

Ich würde als Antwort ein Beispiel für eine FO-Abfrage akzeptieren, die bei der Berechnung der von mir beschriebenen beziehungsfreien Struktur mit einem Element als Instanz von TQBF eindeutig keinen Sinn ergibt. (Ich schlage vor, dass es keine gibt. Wenn Sie also zeigen können, dass es eine gibt, wäre dies ein Gegenbeispiel.)

Vielen Dank.

Das Entscheiden der nichttrivialen Eigenschaften von (einer Indizierungs-) Menge in einer Komplexitätsklasse ist ebenso schwierig wie das Berechnen des Graphen der universellen Funktion für die Klasse. Intuitiv bedeutet dies, dass die einzige Möglichkeit, eine nicht triviale Eigenschaft zu bestimmen, darin besteht, die Maschinen zu simulieren und auf Antworten zu warten. Es scheint mir, dass die Idee, eine solche Eigenschaft zu verwenden, nur das liefert, was unter den Hierarchiesätzen bekannt ist. (Siehe Satz 4.2 von D. Kozen, " Indizierung subrekursiver Klassen ", 1978 für Einzelheiten und die genaue Aussage des Satzes.)

$grU_{AC^0}$$AC^0$$PSpace$$AC^0 \subseteq L$$L$$PSpace$$AC^0$$AC^0$$FO$$PSpace$$PSpace$$AC^0$$AC^0$$PSapce$

$AC^0 \subseteq L \subset PSpace$