Le problème de décider si un CNF monotone implique un DNF monotone

14

Considérez le problème de décision suivant

Entrée : un CNF Φ monotone et un DNF monotone Ψ.

Question : ΦΨ une tautologie?

Vous pouvez certainement résoudre ce problème en temps O(2npoly(l)) , où n est le nombre de variables dans ΦΨ et l est la longueur de l'entrée. D'un autre côté, ce problème est coNP-complet. En outre, une réduction qui établit également coNP-complétude montre que, à moins que SETH échoue, il n'y a pas O(2(1/2ε)npoly(l))-algorithme de temps pour ce problème (cela vaut pour tout positif ε). Voici cette réduction. Soit A un CNF (non monotone) et soit x sa variable. Remplacez chaque occurrence positive de x par y et chaque occurrence négative de x par z . Faites de même pour chaque variable. Soit le CNF monotone résultant Φ . Il est facile de voir que A est satisfiable si Φyz n'est pas une tautologie. Cette réduction fait exploser le nombre de variables d'un facteur 2, ce qui implique 2n/2 Limite inférieure (basée sur SETH) mentionnée ci-dessus.

Il y a donc un écart entre 2n/2 et 2n . Ma question est de savoir si un meilleur algorithme ou une meilleure réduction de SETH est connu?

Juste deux remarques apparemment liées au problème:

  • un problème inverse de savoir si un DNF monotone implique un CNF monotone est trivialement résoluble en temps polynomial.

  • Fait intéressant, le problème de décider si Φ et Ψ calculer la même fonction peut être résolu en temps quasi-polynomiale en raison de Fredman et Khachiyan (la complexité de dualisation de Monotone disjonctif formes normales, Journal des algorithmes 21 (1996), no. 3 , p. 618–628, doi: 10.1006 / jagm.1996.0062 )

Sasha Kozachinskiy
la source

Réponses:

6

En supposant SETH, le problème n'est pas résoluble dans le temps O(2(1ϵ)npoly(l)) pour tout ϵ>0 .


Tout d'abord, permettez-moi de montrer que cela est vrai pour le problème plus général où Φ et Ψ peuvent être des formules monotones arbitraires. Dans ce cas, il y a une réduction ctt poly-temps de TAUT au problème qui préserve le nombre de variables. Soit Ttn(x0,,xn1) la fonction seuil

Ttn(x0,,xn1)=1|{i<n:xi=1}|t.
En utilisant le réseau de tri Ajtai – Komlós – Szemerédi,Ttn peut être écrit par une formule monotone de taille polynomiale, constructible en tempspoly(n).

Étant donné une formule booléenne , nous pouvons utiliser les règles de De Morgan pour l'écrire sous la forme ϕ ( x 0 , , x n - 1 , ¬ x 0 , , ¬ x n - 1 ) ,ϕ est monotone. Alors ϕ ( x 0 , , x n -ϕ(x0,,xn1)

ϕ(x0,,xn1,¬x0,,¬xn1),
ϕest une tautologie si et seulement si les implications monotones T n t ( x 0 ,, x n - 1 ) ϕ ( x 0 ,, x n - 1 , N 0 ,, N n - 1 ) sont valables pour touttn, où N i = T n - 1 t (ϕ(x0,,xn1)
Ttn(x0,,xn1)ϕ(x0,,xn1,N0,,Nn1)
tn
Ni=Ttn1(x0,,xi1,xi+1,,xn1).

Pour l'implication de gauche à droite, soit une affectation satisfaisant T n t , c'est-à-dire avec au moins t uns. Il existe e e avec exactement t uns. Alors e N i¬ x i , donc e ϕ implique e ϕ ( x 0 , , x n - 1 , N 0 , eTtnteeteNi¬xieϕ . Comme il s'agit d'une formule monotone, nous avons également eeϕ(x0,,xn1,N0,,Nn1) . L'implication de droite à gauche est similaire.eϕ(x0,,xn1,N0,,Nn1)


Maintenant, permettez-moi de revenir au problème d'origine. Je vais montrer ce qui suit: si le problème est résoluble dans le temps , alors pour toutk,k-DNF-TAUT (ou dualement,k-SAT) est résoluble dans le temps 2 δ n + O ( 2δnpoly(l)kkk. Cela impliqueδ1si SETH est vrai.2δn+O(knlogn)poly(l)δ1

Supposons donc qu'on nous donne un -DNF ϕ = i < l ( j A i x jj B i ¬ x j ) ,| A i | + |k

ϕ=i<l(jAixjjBi¬xj),
pour chaque i . Nous divisons les n variables en n = n / b blocs de taille b |Ai|+|Bi|kinn=n/b chacun. Par le même argument que ci-dessus,ϕest une tautologie si et seulement si les implications u < n T b t u ( x b u , , x b ( u + 1 ) - 1 ) i < l ( j A i x jj B i Nbk1nlognϕ sont valables pour toutn-tuplet0,,tn-1[0,b], où pour toutj=bu+j,0j<b, nous définissons Nj=T b - 1 t u (xbu,,xbu
()u<nTtub(xbu,,xb(u+1)1)i<l(jAixjjBiNj)
nt0,,tn1[0,b]j=bu+j0j<b Nous pouvons écrire T b t comme un CNF monotone de tailleO( 2 b ), donc le LHS de()est un CNF monotone de tailleO(n 2 b ). Sur la droite, on peut écrire N j
Nj=Ttub1(xbu,,xbu+j1,xbu+j+1,,xb(u+1)1).
TtbO(2b)()O(n2b)Nj comme un DNF monotone de taille . Ainsi, en utilisant la distributivité, chaque disjonction de la RHS peut être écrite comme un DNF monotone de taille O ( 2 k b ) , et la RHS entière est une DNF de taille O ( l 2 k b ) . Il s'ensuit que ( ) est une instance de notre problème de taille O ( l 2 O ( k b ) ) en n variables. Par hypothèse, nous pouvons vérifier sa validité dans le temps O (O(2b)O(2kb)O(l2kb)()O(l2O(kb))n . Nous répétons cette vérification pour tous les b n choix det , donc le temps total est O ( ( b + 1 ) n / b 2 δ n + O ( k b ) l O ( 1 ) ) = O ( 2 δ n + OO(2δn+O(kb)lO(1))bnt comme revendiqué.
O((b+1)n/b2δn+O(kb)lO(1))=O(2δn+O(knlogn)lO(1))

Nous obtenons une connexion plus étroite avec le (S) ETH en considérant la version à largeur limitée du problème: pour tout , soit k -MonImp dénote la restriction du problème où Φ est un k -CNF, et Ψ est un k -DNF. Le (S) ETH concerne les constantes s kk3kΦkΨk

sk=inf{δ:k-SUNETTjeME(2δn)},s=souper{sk:k3}.
sk=inf{δ:k-MonjempTjeME(2δn)},s=souper{sk:k3}.
Clairement,
s3s4s1
comme dans le cas SAT. Nous avons aussi
sksk,
et la réduction à double variable de la question montre
sk2sk.
Maintenant, si nous appliquons la construction ci-dessus avec une taille de bloc constante b, on obtient
sksbk+Journal(b+1)b,
Par conséquent
s=s.
En particulier, SETH est équivalent à s=1et ETH est équivalent à sk>0 pour tous k3.
Emil Jeřábek soutient Monica
la source
Merci pour votre réponse! Je suis curieux de savoir s'il est possible de faireΦ et Ψprofondeur constante dans cette construction? À savoir, je ne sais pas si les formules booléennes monotones à profondeur constante de taille sous-exponentielle (ou même les circuits non monotones) sont connues pourTkn(en particulier pour la majorité)? Bien sûr, il y a un2nΩ(1/) borne inférieure pour la profondeur, mais disons 2nla taille serait OK.
Sasha Kozachinskiy
Tkn, et en général tout élément calculable par des formules de taille polynomiale (c'est-à-dire dans NC ^ 1), a circuits de taille 2nO(1/). Voir par exemple cstheory.stackexchange.com/q/14700 . Je devrai penser si vous pouvez les rendre monotones, mais cela semble plausible.
Emil Jeřábek soutient Monica le
D'ACCORD. Premièrement, la construction générique fonctionne bien dans le paramètre monotone: si une fonction a des formules monotones poly-taille, elle a circuits monotones de taille 2nO(1/)poly(n) pour toute 2. Deuxièmement, pourTkn en particulier, il est facile de construire des3 circuits de taille 2O(nJournaln) en divisant l'entrée en blocs de taille Θ(nJournaln).
Emil Jeřábek supports Monica
Actually, pushing this idea a little bit more, it does provide an answer to the original question: assuming SETH, the lower bound holds already for Φ monotone CNF and Ψ monotone DNF. I will write it up later.
Emil Jeřábek supports Monica
I would guess that you can divide all the variables into about n blocks x1,xn and then write Tk1n(x1)Tknn(xn)ϕ for every k1++knn. You can use 2n-size CNF for every threshold function. But then on a right hand side you will have not DNF but a depth-3 formula...
Sasha Kozachinskiy