Calcul des informations sur Max-3SAT

Pour une formule 3CNF laisser soit le nombre de maximal de clauses satisfaites dans toute affectation à . On sait que Max-3SAT est difficile à estimer (sous réserve de P ≠ NP), c'est-à-dire qu'il n'y a pas d'algorithme de polytime dont l'entrée est une formule 3CNF , et dont la sortie est le nombre tel que trouve dans un facteur multiplicatif de , où est une constante positive absolue.$C$$M(C)$$C$$C$$M'$$M(C)$$1+c$$M'$$c>0$

Je pense qu'il est également difficile de calculer pour tout module constant p . Je me demande si la généralisation commune suivante de ces deux faits est vraie: il n'y a pas d'algorithme de polytime dont l'entrée est une formule 3CNF C avec N clauses, et une chaîne de bits de conseil \ log_2 NB , et dont la sortie est M (C) . Ici, B est une constante absolue. En clair, il n'y a pas d'algorithme qui calcule B bits d'information de M (C) .$M(C) \bmod p$C N log 2 N - B M ( C ) B B M ( C $p$$C$$N$$\log_2 N-B$$M(C)$$B$$B$$M(C)$

Je m'excuse si la question a une réponse bien connue, car je ne suis pas un théoricien de la complexité en passant.

Voici un argument selon lequel si vous pouviez résoudre Max 3SAT sur une instance de clause m avec un nombre constant de bits de conseil, la hiérarchie polynomiale s'effondrerait.

Correction d'un problème NP-complet L. D'après le théorème de Cook, nous connaissons une transformation f () des entrées x pour L en formules 3SAT f (x), de sorte que

1) si alorsM ( f ( x ) ) = $x\in L$$M(f(x)) = m$

2) si alorsM ( f ( x ) ) = m - $x\in L$$M(f(x)) = m-1$

où est le nombre de clauses dans .f ( x $m$$f(x)$

Nous avons également un théorème de Kadin, qui dit que, si on donne entrées d'un problème NP-complet, vous avez un algorithme de temps polynomial qui fait des requêtes à un oracle NP et détermine la bonne réponse aux problèmes de NP , alors la hiérarchie polynomiale s'effondre.x 1 , … , x k ≤ k - 1 k x i ∈ ? $k$$x_1,\ldots,x_k$$\leq k-1$$k$$x_i \in ? L$

Supposons que nous ayons un algorithme qui résout Max SAT sur les entrées de la clause m avec k bits de conseil. Nous utiliserons le résultat de Hastad pour construire un algorithme comme dans la prémisse du théorème de Kadin.

Début de la entrées à problème . Appliquez le théorème de Cook à chacun d'eux. Après une certaine normalisation (ce qui peut être fait en attribuant des poids aux clauses, ou en les dupliquant si nous ne voulons pas utiliser de poids), nous construisons formules où, pour un certain :x 1 , … , x K L K F 1 , … , F K$K=2^k+1$$x_1,\ldots,x_K$$L$$K$$F_1,\ldots,F_K$$m$

1) si et sinonx 1 ∈ L M ( F 1 ) = m - $M(F_1)= m-1$$x_1 \in L$$M(F_1) = m-2$

2) si et sinon$M(F_2) = m\cdot (m-1)$M ( F 2 ) = m ⋅ ( m - 2 $x_2 \in L$$M(F_2) = m\cdot (m-2)$

...

k) si et sinonx K ∈ L M ( F K ) = m K - 1 ⋅ ( m - 2 $M(F_K) = m^{K-1} \cdot (m-1)$$x_K\in L$$M(F_K) = m^{K-1} \cdot (m-2)$

Maintenant , prenez l'union des formules qui ont été construites sur des ensembles de variables disjoints, et appelez . Nous avons donc , et nous pouvons "lire" la réponse aux problèmes en regardant la représentation en base de . Si nous pouvons calculer avec bits de conseil, cela signifie que nous pouvons trouver valeurs telles que l'une d'entre elles est . On peut alors demander de manière non adaptative à un oracle NP si pour chacune des valeurs candidatesM ( F ) = M ( F 1 ) + ⋯ + M ( F k ) K x i ∈ ? L m M ( F ) M ( F ) k 2 k M ( F ) M ( F ) ≥ n i n 1 , … , n 2 k 2 k + 1 $F$$M(F) = M(F_1) + \cdots + M(F_k)$$K$$x_i \in? L$$m$$M(F)$$M(F)$$k$$2^k$$M(F)$$M(F) \geq n_i$$n_1,\ldots,n_{2^k}$nous avons généré. Nous avons donc pu résoudre instances de problèmes NP-complets en effectuant requêtes non adaptatives sur un oracle NP, ce qui implique que la hiérarchie polynomiale s'effondre.$2^k+1$$2^k$

En utilisant le théorème de Hastad au lieu du théorème de Cook, il est possible de pousser la taille de à au lieu de , il est donc possible de pousser à , et le nombre de bits de conseil à . Comprendre ce qui se passe lorsque vous recevez des bits de conseil semble vraiment difficile.O ( 1 ) k ⋅ m m k k log m log log m log m - O ( 1 $F$$O(1)^k \cdot m$$m^k$$k$$\log m$$\log\log m$$\log m - O(1)$

Édité pour ajouter: Krentel ( The Complexity of Optimization Problems . J. Comput. Syst. Sci. 36 (3): 490-509 (1988) ) a prouvé que le calcul de la valeur de l'optimum du problème de clique maximum est complet pour , la classe de fonctions calculables en temps polynomial avec des requêtes vers un oracle NP. L'intégralité est sous "une réduction de requête", dans laquelle la fonction f est réductible à la fonction g si l'on peut écrire pour le temps polynomial calculable et . On peut supposer que la même chose est vraie pour Max Clique. Maintenant, si Max Clique avait un algorithme de temps polynomial qui produit une liste de O ( l o g n ) f ( x ) = r 1 ( g ( r 2 ( x ) ) r 1 r 2 m o ( 1 ) F P N P [ o ( l o g n ) $FP^{NP[O(log n)]}$$O(log n)$$f(x) = r_1(g(r_2(x))$$r_1$$r_2$$m^{o(1)}$les valeurs possibles, ce serait dans , car vous pourriez utiliser la recherche binaire pour trouver l'optimum avec un certain nombre de requêtes qui est un journal de la taille de la liste.$FP^{NP[o(logn)]}$

Maintenant, si nous avons nous aurions certainement , qui est le cas particulier des problèmes de décision, et qui est connu, par les résultats de Wagner (améliorant un résultat de Kadin qui s'applique à un nombre constant de requêtes), pour réduire la hiérarchie polynomiale. Mais je pense que l'on pourrait savoir que impliquerait en fait P = NP. Mais en tout cas, les résultats de Krentel et Kadin-Wagner devraient suffire à donner une autre preuve du résultat d'Andy Drucker. Maintenant, je me demande si c'est en fait la même preuve, c'est-à-dire si le résultat de Fortnow-Van Melkebeek fonctionne, explicitement ou implicitement, via un argument "simulation de requêtes NP avec moins de requêtes NP". P N P [ O ( l o g n ) ] = P N P [ o ( l o g n ) ] F P N P [ O ( l $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$$P^{NP[O(log n)]} = P^{NP[o(log n)]}$$FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$

Un bon document d'enquête qui explique ce qui se passe avec les problèmes d'optimisation et les classes de requête bornées:

http://www.csee.umbc.edu/~chang/papers/bqabh/npfsat.pdf

Je voudrais indiquer une raison pour laquelle il est difficile de prouver la dureté NP de ce problème.

Dans un commentaire sur la question, Luca Trevisan a donné une belle façon de reformuler le problème: le problème suivant est-il résoluble en temps polynomial pour chaque constante k ? Étant donné une formule CNF C avec m clauses, affichez au plus m / k entiers de sorte que l'un d'entre eux soit égal à M ( C ). Ici k est lié à B par k = 2 ^B .

Cependant, demandons plus. À savoir, nous considérons le problème suivant: étant donné une formule CNF C , sortir deux entiers de sorte que l'un d'entre eux soit égal à M ( C ). Nous désignons ce problème par Π. Le problème Π est au moins aussi difficile que le problème d'origine, donc si le problème d'origine est NP-dur, Π doit également être NP-dur.

Notez que Π est un problème de relation. L'un des types de réductions les plus simples qui peuvent être utilisés pour réduire un problème L à un problème de relation Π est une réduction de Levin en temps polynomial, qui est un cas particulier d'une réduction de Turing en temps polynomial où la réduction appelle l'oracle pour Π seulement une fois que.

Nous affirmons que P ^{Π [1]} = P. Cela implique évidemment que NP⊈P ^{Π [1] à} moins que P = NP, c'est-à-dire que Π ne soit pas NP-dur sous la réductibilité de Levin en temps polynomial à moins que P = NP.

Preuve . Soit L ∈P ^{Π [1]} , ou en d'autres termes, il existe une réduction Levin de L à Π. Cela signifie qu'il existe une paire ( f , g ) d'une fonction calculable polynomiale f : {0,1} ^* → {0,1} ^* qui mappe chaque instance x du problème L à une formule CNF f ( x ) et un prédicat calculable en temps polynomial g : {0,1} ^* × ℕ × ℕ → {0,1} tel que g ( x , i , j ) = L( x ) si i ou j est égal à M ( f ( x )). (Ici L ( x ) = 1 si x est une instance oui de L et L ( x ) = 0 si x est une instance non.)

Nous construisons un algorithme polynomial pour L à partir de cela comme suit. Soit x une entrée.

1. Soit C = f ( x ), et que m est le nombre de clauses C .
2. Trouvez un i ∈ {0,…, m } tel que la valeur g ( x , i , j ) soit constante indépendante de j ∈ {0,…, m }.
3. Sortez cette constante g ( x , i , 0).

Dans l'étape 2, un tel i existe toujours car i = M ( f ( x )) satisfait la condition. De plus, cet algorithme ne peut pas produire une mauvaise réponse car g ( x , i , M ( f ( x ))) doit être la bonne réponse. Par conséquent, cet algorithme résout correctement L. QED .

Si je ne me trompe pas, la même idée peut être utilisée pour prouver que P ^{Π [ k ( n )]} ⊆DTIME [ n ^{O ( k ( n ))} ]. Cela implique que NP⊈P ^{Π [ k ]} pour toute constante k sauf P = NP et que NP thatP ^{Π [polylog]} sauf NP unlessDTIME [2 ^polylog ]. Cependant, cette idée seule ne semble pas exclure la possibilité que Π soit NP-dur sous la réductibilité de Turing en temps polynomial.

Je crois que nous pouvons montrer:

Prétendre. Il y a une valeur telle que ce qui suit est vrai. Supposons qu'il existe un algorithme de temps poly déterministe qui, étant donné une instance de clause 3-SAT , génère une liste d'au plus , telle que ; puis la hiérarchie polynomiale s'effondre.m ϕ S m c M ( ϕ ) ∈ $0 < c < 1$$m$$\phi$$S$$m^c$$M(\phi) \in S$

La preuve utilise les résultats de Fortnow et Santhanam sur l' infaisabilité de la compression d'instance de leur article http://www.cs.uchicago.edu/~fortnow/papers/compress.pdf

Plus précisément, en regardant leur preuve de Thm 3.1, je pense que l'on peut extraire ce qui suit (je revérifierai bientôt):

"Théorème" [FS]. Il existe des entiers tels que ce qui suit est vrai. Supposons que dans le poly-temps déterministe, on puisse transformer un OU de formules booléennes (chacune de longueur , et sur des ensembles de variables disjoints) en un OU de formules (là encore variable-disjoint et de longueur ), préservant la satisfiabilité / insatisfiabilité de la RO. Alors et la hiérarchie polynomiale s'effondre.n d ≤ n n d ′ ≤ n N P ⊆ c o N P / p o l $0 < d' < d$$n^d$$\leq n$$n^{d'}$$\leq n$$\mathsf{NP} \subseteq \mathsf{coNP/poly}$

La preuve de notre affirmation sera une réduction de la tâche de compression OR mentionnée dans le théorème [FS] ci-dessus, au problème du calcul de liste . Supposons que est une liste de formules dont OU nous voulons compresser.ψ 1 , … , ψ n $M(\phi)$$\psi_1, \ldots, \psi_{n^d}$

Première étape: définir un circuit de taille polynomiale sur les chaînes d'entrée . Ici, la chaîne code une affectation à , et code un nombre compris entre et .( v , y 1 , … , y n d ) y i ψ i v ∈ { 0 , 1 } d log n + 1 0 n $\Gamma$$(v, y_1, \ldots, y_{n^d})$$y_i$$\psi_i$$v \in \{0, 1\}^{d \log n + 1}$$0$$n^d$

Nous avons accepter si , ou .v = 0 ψ v ( y v ) = $\Gamma$$v = 0$$\psi_v(y_v) = 1$

Soit maintenant la valeur maximale , telle que le circuit restreint est satisfaisable. (Cette quantité est toujours d'au moins 0).v Γ ( v , ⋅ , … , ⋅ $M^*(\Gamma)$$v$$\Gamma(v, \cdot, \ldots, \cdot)$

Supposons que nous pouvons produire efficacement une liste de valeurs possibles pour . Ensuite, la revendication est que dans notre liste , nous pouvons jeter tous les pour lesquels ; la liste résultante contient une formule satisfaisante si celle d'origine ne le faisait. J'espère que cela est clair par inspection.M ∗ ( Γ ) ψ 1 , … , ψ n d ψ i i ∉ $S$$M^*(\Gamma)$$\psi_1, \ldots, \psi_{n^d}$$\psi_i$$i \notin S$

Conclusion: nous ne pouvons pas produire de manière fiable une liste de valeurs possibles pour , sauf si la hiérarchie poly s'effondre.≤ n d ′ M ∗ ( Γ $S$$\leq n^{d'}$$M^*(\Gamma)$

Deuxième étape: on réduit le problème du calcul de liste à celui du calcul de liste pour les instances 3-SAT .M ( ϕ ) $M^*(\Gamma)$$M(\phi)$$\phi$

Pour ce faire, nous exécutons d'abord la réduction de Cook sur pour obtenir une instance 3-SAT de taille . a le même ensemble de variables que , avec quelques variables auxiliaires. Plus important pour nos besoins, est satisfiable ssi est satisfiable.ϕ 1 m = p o l y ( n d ) ϕ 1 Γ ϕ 1 ( v , ⋅ ) Γ ( v , ⋅ $\Gamma$$\phi_1$$m = poly(n^d)$$\phi_1$$\Gamma$$\phi_1(v, \cdot)$$\Gamma(v, \cdot)$

Nous appelons les «fortes contraintes». Nous donnons à chacune de ces contraintes un poids de (en ajoutant des contraintes en double). 2 $\phi_1$$2m$

Ensuite, nous ajoutons un ensemble de «contraintes faibles» qui ajoutent une préférence pour que l'indice (défini à l'étape 1) soit aussi élevé que possible. Il existe une contrainte pour chaque bit de , à savoir . On laisse le ème bit de plus significatif avoir une contrainte de poids . Puisque est de longueur , ces poids peuvent être rendus entiers (il suffit de remplir pour que soit une puissance de 2). v v t v [ v t = 1 ] t v m / 2 t - 1 v d log n + 1 $\phi_2$$v$$v_t$$v$$[v_t = 1]$$t$$v$$m/2^{t-1}$$v$$d \log n + 1$$m$

Enfin, que soit la sortie de notre réduction.$\phi = \phi_1 \wedge \phi_2$

Pour analyser , soit l'ensemble de variables de , avec comme précédemment. Notons tout d'abord que, étant donné toute affectation à , on peut déduire la valeur de partir de la quantité (poids total des contraintes satisfaites par ). Cela découle de la conception hiérarchique des poids de contrainte (de manière similaire à une technique de la réponse de Luca). De même, la valeur maximale réalisable est atteinte par un paramètre qui satisfait toutes les contraintes fortes, et où (sous réserve de cela)( v , z ) ϕ v ( v , z ) v N ( v , z ) = ϕ v , z M ( ϕ ) ( v , z ) v v Γ ( v , ⋅ ) M ∗ ( Γ ) v = Γ ( v , ⋅ $\phi$$(v,z)$$\phi$$v$$(v, z)$$v$$N(v, z) =$$\phi$$v, z$
$M(\phi)$$(v, z)$$v$est aussi grand que possible. Ce est le plus grand indice pour lequel est satisfiable, à savoir . (Remarque, il est toujours possible, en définissant all-0, de satisfaire toutes les contraintes fortes, car dans ce cas, est satisfiable.)$v$$\Gamma(v, \cdot)$$M^*(\Gamma)$$v =$$\Gamma(v, \cdot)$

Il s'ensuit que, si l'on nous donne une liste de valeurs possibles de , nous pouvons dériver une liste devaleurs possibles de . Ainsi, nous ne pouvons pas avoir sauf si la hiérarchie poly s'effondre. Cela donne la revendication, puisque .M ( ϕ ) | S | M ∗ ( Γ ) | S | ≤ n d ′ n d ′ = m Ω ( 1 $S$$M(\phi)$$|S|$$M^*(\Gamma)$$|S| \leq n^{d'}$$n^{d'} = m^{\Omega(1)}$