Dans cette question, une formule 3CNF signifie une formule CNF où chaque clause implique exactement trois variables distinctes . Pour un 0 < s <1 constant , Gap-3SAT s est le problème de promesse suivant:
Gap-3SAT de
l' instance : A 3CNF formule de φ.
Oui-promesse : φ est satisfaisable.
Pas de promesse : aucune assignation de vérité ne satisfait plus que la fraction s des clauses de φ.
L'une des façons équivalentes d'énoncer le célèbre théorème PCP [AS98, ALMSS98] est qu'il existe une constante 0 < s <1 telle que Gap-3SAT s est NP-complet.
Nous disons qu'une formule 3CNF est bornée par paire B si chaque paire de variables distinctes apparaît dans la plupart des clauses B. Par exemple, une formule 3CNF ( x 1 ∨ x 2 ∨ x 4 ) ∧ (¬x 1 ∨¬x 3 ∨ x 4 ) ∧ ( x 1 ∨ x 3 ∨¬x 5 ) est paire par 2 mais pas par paire 1 - borné parce que par exemple la paire ( x 1 , x 4 ) apparaît dans plus d'une clause.
Question . Faire il existe des constantes B ∈ℕ, un > 0, et 0 < s <1 de telle sorte que l' écart-3SAT s est NP-complet , même pour une formule 3CNF qui est pairwise B -bounded et se compose d'au moins une 2 clauses, où n est le nombre de variables?
La délimitation par paires implique clairement qu'il n'y a que des clauses O ( n 2 ). Avec la borne inférieure quadratique du nombre de clauses, il indique grossièrement qu'aucune paire de variables distinctes n'apparaît dans beaucoup plus de clauses que la moyenne.
Pour Gap-3SAT, on sait que le cas clairsemé est difficile : il existe une constante 0 < s <1 telle que Gap-3SAT s est NP-complet même pour une formule 3CNF où chaque variable apparaît exactement cinq fois [Fei98]. D'un autre côté, le cas dense est facile : Max-3SAT admet un PTAS pour une formule 3CNF avec Ω ( n 3 ) clauses distinctes [AKK99], et donc Gap-3SAT s dans ce cas est en P pour chaque constante 0 < s <1. La question porte sur le milieu de ces deux cas.
La question ci-dessus s'est posée à l'origine dans une étude de la complexité de calcul quantique, plus spécifiquement des systèmes de preuve interactifs à un tour à deux proverseurs avec des provers entremêlés (systèmes MIP * (2,1) ). Mais je pense que la question peut être intéressante en soi.
Les références
[AKK99] Sanjeev Arora, David Karger et Marek Karpinski. Schémas d'approximation du temps polynomial pour une instance dense de problèmes NP-difficiles. Journal of Computer and System Sciences , 58 (1): 193–210, février 1999. http://dx.doi.org/10.1006/jcss.1998.1605
[ALMSS98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Soudan et Mario Szegedy. Vérification des preuves et dureté des problèmes d'approximation. Journal de l'ACM , 45 (3): 501–555, mai 1998. http://doi.acm.org/10.1145/278298.278306
[AS98] Sanjeev Arora et Shmuel Safra. Vérification probabiliste des preuves: Une nouvelle caractérisation de NP. Journal de l'ACM , 45 (1): 70–122, janvier 1998. http://doi.acm.org/10.1145/273865.273901
[Fei98] Uriel Feige. Un seuil de ln n pour approximer la couverture d'ensemble. Journal de l'ACM , 45 (4): 634–652, juillet 1998. http://doi.acm.org/10.1145/285055.285059
la source
Réponses:
Pas une réponse complète, mais j'espère proche. Ceci est très proche des commentaires de Luca ci-dessus. Je crois que la réponse est qu'au moins il existe des constantes B ∈ℕ, a > 0 et 0 < s <1 telles que Gap-3SAT s est NP-complet même pour une formule 3CNF qui est par paires B- bornée et se compose de au moins clause n 2 - ϵ , pour toute constante ϵ .an2−ϵ ϵ
La preuve est la suivante. Considérons un GAP-3SAT par exemple de φ sur N les variables dans lesquelles chaque variable apparaît à la plupart des 5 fois. C'est NP-complet, comme vous le dites dans la question.s ϕ N
Maintenant, nous créons une nouvelle instance comme suit:Φ
Le nombre total de variables est alors . Remarque Φ a 2 N n 2 clauses de comparaison et 5m=nN Φ 2Nn2 clauses héritées, pour un total de1153Nn2 clauses. En prenantn=Nkon am=Nk+1et le nombre total de clausesC=11113Nn2 n=Nk m=Nk+1 . On prendk=ϵ-1-1, doncC∝m2-ϵ.C=113N2k+1=113m2−1k+1 k=ϵ−1−1 C∝m2−ϵ
Ensuite, est délimité par paires 8 (max 2 des clauses de comparaison et 6 des clauses héritées).Φ
Enfin, si n'est pas satisfaisant, alors au moins ( 1 - s ) N clauses ne sont pas satisfaites. Maintenant, si y i a ≠ y i b pour tout a , b alors au moins n - 1 clauses ne sont pas satisfaites. Notez que pour satisfaire les ( 1 - s ) N clauses non satisfaites dans un ensemble de clauses héritées pour fixe a , b alors l'affectation des variables y : a , y :ϕ (1−s)N yia≠yib a,b n−1 (1−s)N a,b y:a et y : ( a + b ) doivent différer d'au moins 1 - sy:b y:(a+b) positionsN, laissant au moins1-s1−s5N comparaison clauses insatisfaisantes. Cela doit être valable pour chaque choix deaetb, donc au moins≈1-s1−s5N(n−1) a b clauses de comparaisonCdoivent rester insatisfaites au total pour que suffisamment de clauses héritées soient satisfaites. Si toutefois vous regardez l'autre extrême où toutes les clauses de comparaison sont satisfaites, alors(1-s)Nn2=(1-s)m 2 k + 1≈1−s5Nn2=3(1−s)11C clausesC nesont pas satisfaisantes. Il reste donc un écart (bien que réduit) avecs′=4+s(1−s)Nn2=(1−s)m2k+1k+1=(1−s)C .s′=4+s5
Les constantes doivent probablement être revérifiées.
la source