Quantificateurs universels dans QBFS

Question

Je cherche des réductions vers / depuis la langue TQBF et j'ai réussi à rester coincé sur quelque chose qui n'est presque certainement pas vrai (ou si cela est vrai, il me manque un coût de calcul important qui lui est associé) avec respect de simplifier les instances TQBF.

Pour des raisons de simplicité, limitons l'attention sur les instances TQBF dans la forme normale de Prenex et le CNF sans variables libres. Mon hypothèse (que je soupçonne fortement d'être fausse, mais j'ai été incapable de trouver un contre-exemple) est qu'un tel TQBF est satisfible si et uniquement si le TQBF résultant de la suppression de toutes les instances de variables universellement quantifiées de la peine est satisfaite. Par exemple, prenez l'instance suivante:

$ \ existe a \ Forall b \ existe c \ Forall d $ $ \ psi (a, b, c , d) $

$ \ psi (a, b, c, d)= (\ nge a \ vee b \ vee c) \ coin (\ neg b \ vee \ neg c \ vee d) \ wedge (a \ vee c \ vee \ neg d) $

Premièrement, je soutiens que cette instance n'est pas satisfible (facilement vérifiable à la main). Si nous appliquons la méthode que je décris ci-dessus, nous obtenons le "noyau" suivant:

$ \ existe une \ Existe C $ C $ $ \ phi (a, c) $ , < / p>

$ \ phi (a, c)= (\ nge a \ vee c) \ wedge (\ nge c) \ coin (a \ vee c) $

qui n'est clairement pas satisfible. Si au lieu de cet exemple, nous examinons ceci:

$ \ existe a \ Forall b \ existe c \ Forall d $ $ \ psi (a, b, c , d) $

$ \ psi (a, b, c, d)= (\ nge a \ vee b \ vee \ neg c) \ wedge (\ neg b \ vee c \ vee d) \ wedge (a \ vee c \ vee \ neg d) $

quel est clairement satisfait (ensemble C à true, A à False) et qui a un "noyau" de

$ \ existe une \ Existe C $ C $ $ \ phi (a, c) $ , < / p>

$ \ phi (a, c)= (\ nge a \ vee \ ng c) \ coin (c) \ coin (a \ vee c) $

qui est également satisfible avec les mêmes paramètres variables.

Si cette méthode fonctionne toujours, cela semblerait impliquer qu'il existe une réduction de la TQBF à siéger dans le temps linéaire dans le nombre de quantificateurs universels et le nombre d'occurrences des variables universellement quantifiées dans la formule, montrant que TQBF est NP-Complete (il est déjà connu pour être complet de PSPACE-complet et donc NP-DUR, donc s'il est dans NP, il est NP-complet) et en outre que NP= pSPACE. Je serais complètement abasourdi si tel est le cas, mais je n'ai pas été incapable de trouver un contre-exemple (ou un coût de calcul manquant dans la réduction qui ne le rend pas du temps polynomial). Qu'est-ce que je manque?

Answer 1

Votre intuition avait raison. Ça ne marche pas. Voici un contre-exemple.

considérer $ \ existez a \ existez b \ varphi (a, b) $ où $ \ Varphi (A, b)= (a \ lor \ neg b) \ terre (\ nge a \ lor b) $ . Cette déclaration évalue à vrai.

Cependant, si nous supprimons $ a $ suivant votre procédure, nous obtenons $ \ psi (b) $ où $ \ psi (b)= (((\ nge b) \ terres (b)) $ ; et cette déclaration s'évalue sur FALSE.

Un moyen de comprendre pourquoi votre méthode ne fonctionne pas est que $ \ existez a \ existez b \ varphi (a, b) $ n'est pas équivalent à $ \ existe b \ Forall a \ Varphi (A, B) $ . Au plus, votre méthode pourrait fonctionner si tout $ \ FORLEZ $ S est à l'intérieur, c'est-à-dire pour une phrase de la forme $ \ exist \ CDOT \ Existe \ Forall \ Cdots \ Forall $ , mais pas pour un autre modèle de $ \ existez et $ \ Forall $ .