Une version descriptive de la complexité du théorème de Rice pourrait-elle être utilisée pour séparer AC0 et PSPACE?

10

Dans cette question , il a été mentionné qu'il existe des versions de complexité descriptive du théorème de Rice. J'ai trouvé une preuve du théorème suivant:

Étant donné une classe de complexité C , les propriétés non triviales des langages en C ne peuvent pas être calculées en C

J'avais déjà posté la preuve que j'ai trouvée, mais parce qu'elle était si longue et parce qu'il a été souligné dans les commentaires que cet article contient déjà une preuve de ce théorème, je l'ai retirée. (Si, pour une raison quelconque, vous voulez désespérément voir ma preuve, veuillez consulter les révisions précédentes de cette question.)

Mon intérêt est de savoir si ce théorème pourrait être utilisé pour séparer AC0 et PSPACE. Voici l'argument:

Considérons la propriété P de la classe de complexité AC0 définie comme suit:

P : la propriété d'être une requête FO qui accepte une structure fixe particulière, à savoir la structure composée d'un élément, sans fonctions, sans constantes et sans relations

Clairement, par le théorème ci-dessus, P n'est pas décidable dans AC0; c'est une propriété non triviale des requêtes FO.

Cependant, un petit examen devrait montrer que calculer si oui ou non une requête FO accepte une structure aussi simple peut être décidé aussi facilement que TQBF; ainsi, P est décidable dans PSPACE.

Pour assurer la clarté sur ce point (que P est calculable dans PSPACE): Notez que la propriété qui nous intéresse nécessite que la structure soit FO. Donc, nous essayons de déterminer si une requête FO qui s'exécute sur une structure à élément unique sans relations accepte. Puisqu'il n'y a aucune relation à traiter, il doit être clair que la tâche de décider d'une telle requête FO équivaut à décider une instance de TQBF; il n'y a pas de relations, donc le seul défi qui reste est d'évaluer si oui ou non la formule booléenne quantifiée est vraie. Il s'agit essentiellement de TQBF, donc P est calculable dans PSPACE.

Parce que P est calculable dans PSPACE mais pas AC0, nous devrions pouvoir conclure que AC0! = PSPACE. Ce raisonnement est-il correct ou ai-je fait une erreur quelque part? Je suis particulièrement préoccupé par le paragraphe précédent; J'essaierai de clarifier et de mettre à jour l'argument demain après avoir eu l'occasion de réfléchir un peu plus à l'exposition.

J'accepterais comme réponse un exemple d'une requête FO qui, lors du calcul sur la structure sans relation à un élément que j'ai décrite, n'a clairement aucun sens en tant qu'instance de TQBF. (Je suggère qu'il n'y en a pas, donc si vous pouvez montrer qu'il y en a un, ce serait un contre-exemple.)

Merci.

cc.complexity-theory complexity-classes descriptive-complexity separation Philip White
la source
@Kaveh: Vous devriez faire de votre commentaire une réponse.
Dai Le
@Kaveh: Merci pour votre commentaire. Je suis cependant un peu confus par ce que vous dites. De quelle machine PSPACE pour les ensembles AC0 parliez-vous? Je faisais référence à la propriété P, qui se rapporte spécifiquement aux requêtes FO sur des structures très simples. Je suggère qu'évaluer si les requêtes FO acceptent une structure simple est garanti comme étant TQBF, qui est PSPACE. Je ne vois pas où un simulateur universel pour AC0 est nécessaire.
Philip White
@Kaveh: OK. Je vais préparer ma tentative de preuve de la conjecture dans cette question et l'afficher comme une question distincte. Je pensais que c'était correct, mais je me trompe souvent. (Bien sûr, si vous réfutez ma conjecture avant cela, je ne m'en préoccuperai pas.)
Philip White
Oh. Je viens de le poster sous forme de question. Dois-je supprimer la nouvelle question et la publier comme réponse?
Philip White
(Je l'ai supprimé et ajouté à cette question.)
Philip White

Réponses:

7

Décider des propriétés non triviales (d'une indexation) d'ensembles dans une classe de complexité est aussi difficile que de calculer le graphique de la fonction universelle pour la classe. Intuitivement, cela signifie que la seule façon de décider d'une propriété non triviale est de simuler les machines et d'attendre les réponses. Il me semble que l'idée d'utiliser une telle propriété ne fera que donner ce que les théorèmes de hiérarchie connaissent. (Voir le théorème 4.2 de D. Kozen, " Indexing of subrecursive classes ", 1978 pour les détails et l'énoncé exact du théorème.)

grUAC0AC0PSpaceAC0⊆LLPSpaceAC0AC0FOPSpacePSpaceAC0AC0PSapce

AC0⊆L⊂PSpace

Kaveh
la source
Intéressant, merci. Vous dites donc: 1) mon argument était juste, mais 2) il y avait un moyen plus simple. :) Je suppose que je dois rafraîchir le théorème de la hiérarchie spatiale.
Philip White
FO
OK super. En fait, je viens de vérifier la définition de FO. Je savais qu'il comprenait le symbole de l'égalité; c'est pourquoi j'ai exigé que la structure soit un seul élément. De cette façon, toute déclaration sur l'égalité de deux variables n'aura pas d'impact sur la vérité de la requête.
Philip White
Un commentaire supplémentaire ... vous avez fait un point important au sujet des symboles non logiques. Parce qu'il n'y a pas de relations, le symbole de l'égalité est en fait essentiel. En particulier, il est nécessaire d'exprimer les littéraux très booléens nécessaires à l'expression de TQBF.
Philip White
FO