Tailles PCP asymptotiques les plus connues / 3-SAT

Quelles sont les limites supérieures asymptotiques les plus connues sur les tailles des preuves vérifiables de manière probabiliste? Idéalement, je recherche une enquête contemporaine sur cette large question, mais s'il n'y en a pas, je suis particulièrement intéressé par l'inapproximabilité du 3-SAT.

Soit 7/8 + ε-3-SAT soit 3-SAT avec la promesse que si la fraction 7/8 + ε des clauses est satisfiable, alors l'instance est satisfiable. Quelles sont les réductions les plus connues de 3-SAT avec clauses à 7/8 + ε-3-SAT? Par exemple, y a-t-il une réduction en utilisant les clauses ? ( clauses sont un problème ouvert.) Une réduction de la taille quasi-linéaire uniforme NC? Quelle est la dépendance de , y compris lorsque ? Existe-t-il une réduction linéaire connue (dépendante de ) de (1-ε) -3-SAT à 7/8 + ε-3-SAT, et sinon, avons-nous de meilleures limites pour (1-ε) -3 -SAM? Même une réponse partielle serait intéressante. $n$ $O(n \log n)$ $O(n)$ $ε$ $ε→0$ $ε$

En outre, même si cela rendrait peut-être la question trop large, je dois mentionner qu'un autre problème important ici est les facteurs constants, qui, en raison de techniques telles que le code long, sont généralement incroyablement volumineux.

cc.complexity-theory reference-request np-hardness pcp Dmytro Taranovsky
la source

Réponses:

L'état de l'art pour les PCP qui produisent une réduction à 3-SAT (même pour la sous-constante ) sont ceux de Dana Moshkovitz et Ran Raz , qui avoir la longueur . Je ne sais pas, cependant, si quelqu'un a essayé de calculer la dépendance exacte de la longueur sur , ou la complexité de calcul de la réduction. Leur principal résultat technique a été simplifié plus tard par Irit Dinur et Prahladh Harsha . $(\frac{7}{8}+\varepsilon)$ $\varepsilon$ $n^{1 + o(1)}$ $\varepsilon$

Si vous êtes intéressé par des PCP courts avec un nombre constant de requêtes qui ne donnent pas nécessairement des réductions optimales de la dureté d'approximation (aka "PCP à haute erreur"), alors le résultat le plus récent est des PCP de longueur raison d' Eli Ben-Sasson et de Madhu Soudan et de son amélioration par Dinur . Encore une fois, je ne sais pas si c'est la complexité exacte du calcul de la réduction. $n\cdot \mathrm{poly}\log n$

Ou Meir
la source

Je vous remercie; les deux parties ont été utiles. Je suppose que la PCP de taille quasi-linéaire avec des requêtes O (1) et une erreur constante restent un problème ouvert.

Dmytro Taranovsky

Non, cela découle en fait du travail de Ben-Sasson et du Soudan. C'est un problème ouvert d'obtenir de tels PCP avec une erreur sous-constante.

Ou Meir

J'ai regardé un peu plus et Dinur 2007 étend le document que vous avez cité dans le deuxième paragraphe pour montrer . Si je comprends bien, cela implique une réduction de 3-SAT à une taille quasi linéaire 3-SAT, mais le résultat que vous avez cité dans le premier paragraphe n'est pas redondant car il nous donne 7/8 et plus.

S A T \in P C P_{\frac{1}{2}, 1} [\log_{2} n + O (\log \log n), O (1)]

$SAT ∈ PCP_{\frac{1}{2},1}[\log_2 n + O(\log \log n), O(1)]$

1 - ε

$1-ε$

7 / 8 + ε

$7/8+ε$

Dmytro Taranovsky

Oui c'est correct. J'ai oublié de mentionner le résultat de Dinur, je vais l'ajouter à la réponse.

Ou Meir