Formules booléennes quantifiées avec alternances logarithmiques

15

J'étudie un problème difficile pour la classe des formules booléennes quantifiées avec un nombre logarithmique d'alternances des quantificateurs. Un problème dans cette classe ressemblerait à:

(x1,x2,xa1)(xa1+1,xa2),(xalogn1,xalogn)F

alogn=n , et F est une formule booléenne des variables x1xn .

Cette classe contient clairement PH et est contenu dans AP=PSPACE . Y a-t-il un nom pour cette classe? Y a-t-il quelque chose de plus connu à ce sujet?

isaacg
la source
3
Eh bien, c'est complet pour alterner le temps polynomial avec de nombreuses alternances logarithmiques.
Emil Jeřábek soutient Monica le
2
Une notation convenue pour la classe de complexité de ce problème serait STA ( ,nO(1),O(Journaln) ). Ici, STA (s (n), t (n), a (n)) est la mesure d'alternance espace-temps introduite par Berman dans "La complexité des théories logiques" parue dans TCS en 1980. Cette classe contient toutes les décisions problème décidable par une machine de Turing alternée au temps t (n) utilisant l'espace s (n) et alternant au plus a (n) fois sur chaque branche de calcul. Comme l'a souligné Emil, votre problème devrait être complet pour ce cours.
Christoph Haase
2
AltTime (lg n, poly (n))
Kaveh
N'est-ce pas aussi l'analogue binaire de la classe FOLL introduit par Barrington, Kadau, McKenzie et Lange. FOLL est défini en itérant un bloc FO essentiellement un journal de circuit AC0 uniforme à n entrées et n sorties n fois. Il est trop faible pour calculer la parité mais n'est pas connu pour être contenu dans une classe plus petite que AC ^ 1. Il peut faire un certain nombre de choses non triviales, y compris l'alimentation dans un groupe commutatif présenté comme une table de multiplication. Je voudrais appeler la classe en question PHL car elle correspond à un bloc de PH itéré n fois. Je pense qu'il n'est toujours pas clair s'il est comparable à PSPACE.
SamiD
De plus, si un groupe abélien est donné par un circuit qui prend en entrée deux nombres à n bits et produit un nombre à n bits, alors l'alimentation est en PHL par une preuve similaire à Barrington et al ci-dessus.
SamiD

Réponses:

7

En s'appuyant sur la réponse de Michael Wehar, il semble que vous pouvez facilement montrer que les calculs peuvent être codés en polysize de tels QBF: vous utilisez des alternances O ( log n ) , chacun de p o l y ( n ) bits, et faire un argument similaire au théorème de Savitch. Toutes les deux alternances diviseront le temps d'exécution du calcul par un p o l y ( )NTISP(nlogn,poly(n))O(logn)poly(n)poly(n) facteur.

J'appellerais la classe , en suivant la notation de Fortnow "Time-Space Tradeoffs for Satisfibility" qui pourrait également être citée pour l'argument esquissé dans le paragraphe précédent (mais veuillez consulter le document pour des références antérieures).ΣO(logn)P

Ryan Williams
la source
Merci beaucoup pour le commentaire et la réponse de suivi. J'ai modifié ma réponse et ajouté des détails sur la généralisation de l'argument. Il existe en fait un compromis temps, espace et alternance pour les types de calculs qui peuvent être encodés.
Michael Wehar
Merci pour la référence ajoutée! J'ai également ajouté une réponse plus succincte pour clarifier, espérons-le. Merci encore. :)
Michael Wehar
7

(1) Ce que nous savons déjà:

Comme vous l'avez déjà dit, QBF avec alternances log ( n ) de quantificateurs est difficile pour chaque niveau de la hiérarchie polynomiale.log(n)

(2) Je pense que nous pouvons également prouver ce qui suit:

Le problème est -hard.NSPUNECE(log2(n))

(3) Voici ma justification informelle de l'affirmation précédente:

Étant donné un NTM lié à l'espace et une chaîne d'entrée, nous devons déterminer s'il existe un calcul acceptant sur la chaîne d'entrée donnée.log2(n)

Chaque configuration du calcul peut être représentée par essentiellement 2 bits . En d'autres termes, nous pouvons représenter une configuration par un groupe de variables log 2 ( n ) .Journal2(n)Journal2(n)

L'idée est que nous avons une configuration de départ et une configuration finale et nous devons deviner le calcul qui se produit entre les deux. Nous devinons récursivement les configurations "moyennes" en utilisant des quantificateurs existants et récurrons en vérifiant que la configuration "gauche" va au "milieu" et la configuration "moyenne" va à la "droite" en utilisant pour tous les quantificateurs.

Maintenant, pour que cela fonctionne, au lieu de choisir une configuration "moyenne", nous devons choisir un groupe de configurations "intermédiaires" également espacées entre les configurations "gauche" et "droite". En particulier, on pourrait deviner configurations "intermédiaires" également espacées utilisant des quantificateurs existants avecnvariables, puis récapitulez chaque écart entre les configurations en utilisant pour tous les quantificateurs desvariablesà peu prèslog(n).nlog2(n)Journal(n)

Il suffit de continuer la récursivité jusqu'à la profondeur pour pouvoir couvrir un calcul de longueur 2Journal(n)où chaque configuration a au pluslog2(n)plusieurs bits.n2Journal(n)=nJournal(n)=2Journal2(n)Journal2(n)

Puisque la récursivité est de profondeur , nous n'avons que O ( log ( n ) ) groupes de variables c'est-à-dire des alternances. Puisque chaque groupe de quantificateurs a seulement O(Journal(n))O(Journal(n))variables, au total nous avonsO(nlog2(n)variables.O(nlog3(n))

N'hésitez pas à offrir vos commentaires ou corrections. Merci beaucoup et j'espère que cela vous aidera un peu.

(4) Une affirmation plus générale comme le suggère la réponse de Ryan:

Vous devriez pouvoir exécuter la construction précédente de manière plus générale. Considérer ce qui suit:

À chaque étape de la récursivité, divisez en groupes de configurations «intermédiaires» en utilisant c ( n ) bits par configuration. Ensuite, faites la récursivité à la profondeur d ( n ) .g(n)c(n)d(n)

Tant que nous n'avons pas trop de variables et trop d'alternances, cela semble fonctionner correctement. En gros, nous avons besoin des éléments suivants pour être satisfait:

  • g(n)c(n)d(n)n
  • d(n)log(n)

Notre approche généralisée sera utilisée pour simuler des machines de Turing non déterministes qui fonctionnent pour étapes en utilisant c ( n ) bits de mémoire.g(n)d(n)c(n)

En particulier, nous choisissons les éléments suivants:

  • g(n)=n

  • c(n)=n2log2n

  • d(n)=2log2(n)

Les inégalités précédentes sont satisfaites et nous pouvons réaliser la construction pour simuler des machines de Turing non déterministes qui fonctionnent pour environ étapes log 2 ( n ) en utilisant 2log2(n) bits de mémoire.n2log2n

En d'autres termes, nous avons un meilleur résultat de dureté qu'auparavant. En particulier, le problème est difficile pour .NTISP(2log2(n),n2log2n)

(5) Autres généralisations:

Dans la généralisation précédente, nous simulions des machines de Turing non déterministes temporelles et spatiales. Cependant, nous pouvons être en mesure de simuler également des machines de Turing limitées dans le temps et l'espace.

Permettez-moi de vous expliquer un peu. Nous utilisons donc approximativement alternances log ( n ) pour effectuer la récursivité vers log ( n ) en profondeur . Cependant, nous pourrions utiliser certaines des alternances initialement, disons log(n)log(n) . Ensuite, nous pourrions utiliser le restelog(n) alternances pour aller en profondeurlog(n) .log(n)

Dans ce cas, nous pourrions simuler des machines de Turing alternées qui ont alternances avec des longueurs de témoin sublinéaires, exécutez pour2 log 3log(n)étapes et utilisez2log32(n) bits de mémoire.n2log2n

En d'autres termes, le problème est difficile pour avec des longueurs de témoin sublinéaires. Alternativement, cette classe pourrait être écrite en utilisant lanotationSTAmentionnée dans les commentaires ci-dessus.AltTimeSpace(log(n),2log32(n),n2log2n)STA

Merci pour les commentaires et n'hésitez pas à offrir d'autres corrections ou clarifications. :)

Michael Wehar
la source
1
La dureté ne suivrait-elle pas tout de suite la dureté PH? NL2
Nikhil
1
Comment savons-nous exactement le point (1)? N'avons-nous pas besoin de variables pour atteindre un certain niveau k de PH? Peut-être que je manque un point simple ici. 2kk
Markus
1
@MichaelWehar Bien sûr, mais nous savons que non? Et cela signifie que chaque problème dans N L 2 se réduit à QBF avec constamment de nombreuses alternances, ce qui est un cas particulier des alternances log-many? NL2PHNL2
Nikhil
1
@MichaelWehar Oups. Bien sûr, vous avez raison! Une question connexe ici: cstheory.stackexchange.com/questions/14159/…
Nikhil
2
Pourquoi pas -hard? NTISP(nlogn,poly(n))
Ryan Williams
1

Une réponse plus courte.

Observations initiales:

  • Le problème est difficile à tous les niveaux de la hiérarchie polynomiale.
  • Le problème est difficile pour les machines de Turing alternées avec des alternances qui fonctionnent pendant un temps polynomial.log(n)

Des informations plus approfondies:

  • Suggéré par le commentaire de Kaveh ci-dessus, le problème peut coder les calculs pour les machines Turing.AltTime(log(n),n)
  • De plus, comme Ryan l'a souligné, le problème peut coder des calculs pour NTimeSpace(2log2(n),n)
  • UNEltTjemeSpunece(une(n),t(n),s(n))avec des longueurs de témoins restreintes. Je ne sais pas exactement quelle est la relation exacte entre une(n), t(n), et s(n) doit être, mais nous savons que:

    1. une(n)Journal(n)

    2. t(n)2Journal2(n)

    3. s(n)n

Voir ma réponse plus longue pour plus de détails sur les compromis entre une(n), t(n), et s(n).

Remarque: Dans ce qui précède, quand je dis encoder des calculs, je veux dire encoder le calcul sans trop exploser la taille de l'instance. Autrement dit, si nous explosons den taille Turing machine entrée à poly(n)formule de taille, alors je pense que bien que l'explosion soit polynomiale, il est bon de porter une attention particulière au degré du polynôme. La raison de la perspective à grain semi-fin est d'essayer de mieux reconnaître comment les différentes mesures de la complexitéune(n), t(n), et s(n) dépendent les uns des autres.

Michael Wehar
la source
De plus, il y a un autre facteur que j'ai omis. C'est-à-dire que la taille de témoin utilisée avec chaque alternance prend des variables. En d'autres termes, plus les témoins sont grands, moins nous avons de variables, ce qui signifie que nous ne pouvons potentiellement pas représenter autant de bits par configuration, ce qui nous oblige éventuellement à avoir moins d'espace pour la machine pour laquelle nous codons les calculs.
Michael Wehar
Fondamentalement, toutes les longueurs de témoin pour les quantificateurs sont sublinéaires et la taille que nous pouvons les faire dépend du choix de une(n), t(n), et s(n).
Michael Wehar
Peut-être qu'un quantificateur interne qui existe le plus n'a pas besoin d'avoir une taille de témoin restreinte parce que nous pouvons deviner au fur et à mesure.
Michael Wehar