Algorithmes d'approximation du temps super-polynomiaux pour MAX 3SAT

Le théorème PCP indique qu'il n'y a pas d'algorithme de temps polynomial pour MAX 3SAT pour trouver une affectation satisfaisant 7/8 clauses d'une formule 3SAT satisfaisante à moins que .P = N $7/8+ \epsilon$$P = NP$

Il existe un algorithme de temps polynomial trivial qui satisfait des clauses. Alors, pouvons-nous faire mieux que si nous permettons des algorithmes super-polynomiaux? Quels rapports d'approximation pouvons-nous atteindre avec des algorithmes de temps quasi-polynomiaux ( ) ou avec des algorithmes de temps sous-exponentiels ( )? Je cherche des références à de tels algorithmes.7 / 8 + ε n O ( log n ) 2 o ( n $7/8$$7/8+ \epsilon$$n^{O(\log n)}$$2^{o(n)}$

On peut obtenir une approximation 7/8 pour MAX3SAT qui s'exécute en sans trop de problèmes. Voici l'idée. Divisez l'ensemble de variables en groupes de variables chacun. Pour chaque groupe, essayez toutes les façons d'affecter les variables dans le groupe. Pour chaque formule réduite, exécutez l' approximation Karloff et Zwick . Sortie de l'affectation satisfaisant un nombre maximum de clauses, sur tous ces essais.2 O ( ε n ) O ( 1 / ε ) ε n 2 ε n sept /$7/8+\varepsilon/8$$2^{O(\varepsilon n)}$$O(1/\varepsilon)$$\varepsilon n$$2^{\varepsilon n}$$7/8$

Le fait est qu'il existe un bloc variable tel que l'affectation optimale (limitée à ce bloc) satisfait déjà une fraction du nombre maximal de clauses satisfaites. Vous obtiendrez ces clauses supplémentaires exactement correctes, et vous obtiendrez de la fraction restante de l'optimum en utilisant Karloff et Zwick.7 /$\varepsilon$$7/8$

C'est une question intéressante si l'on peut obtenir temps pour le même type d'approximation. Il existe une "conjecture PCP linéaire" selon laquelle 3SAT peut être réduit en temps polynomial à MAX3SAT, de sorte que:$2^{O(\varepsilon^2 n)}$

• si l'instance 3SAT est satisfiable, alors l'instance MAX3SAT est complètement satisfiable,
• si l'instance 3SAT n'est pas satisfaisante, alors l'instance MAX3SAT n'est pas satisfaisante 7/8 , et$7/8+\varepsilon$
• la réduction augmente la taille de la formule par un seul facteur.$poly(1/\varepsilon)$

En supposant que cette conjecture linéaire PCP, un -temps sept / huit + ε approximation, pour tous les c et ε , n'implique que 3SAT est dans 2 ε n fois, pour tout ε . (Voici m le nombre de clauses.) La preuve utilise le lemme de sparsification d'Impagliazzo, Paturi et Zane.$2^{O(\varepsilon^c m)}$$7/8+\varepsilon$$c$$\varepsilon$$2^{\varepsilon n}$$\varepsilon$$m$

Pour reprendre un peu ce que Ryan Williams a écrit dans son dernier paragraphe:

Le théorème Moshkovitz-Raz montre qu'il existe une fonction de telle sorte que si Max-3Sat peut être ( sept / huit + 1 / ( log log n ) 0,000001 ) -approximated en temps T ( n ) alors la version de décision de 3Sat est dans le temps 2 o ( n $T(n) = 2^{n^{1-o(1)}}$$(7/8 + 1/(\log \log n)^{.000001})$$T(n)$$2^{o(n)}$. Il est communément admis que la seconde est impossible (c'est l'hypothèse de temps exponentielle), auquel cas la première est également impossible. Pour mettre tout à fait exact, vous ne pouvez pas battre pour Max-3Sat en quoi que ce soit mieux que temps plein exponentielle.$7/8$