L'intégration d'une solution est-elle possible pour SAT?

Je m'intéresse aux instances individuelles "dures" de problèmes NP-complets.

Ryan Williams a discuté du problème SAT0 sur le blog de Richard Lipton . SAT0 demande si une instance SAT a la solution spécifique composée de tous les 0. Cela m'a fait penser à la construction d'instances SAT susceptibles d'être "dures".

Considérons une instance SAT avec clauses et variables, où est "assez grand", dans le sens où elle tombe dans la région au-delà de la transition de phase, où presque toutes les instances ne sont pas satisfaisantes. Soit une affectation aléatoire aux valeurs de . $\phi$ $m$ $n$ $\alpha = m/n$ $x$ $\phi$

Est-il possible de modifier pour obtenir une nouvelle instance , de sorte que est "largement similaire" à , mais de sorte que est une affectation satisfaisante pour ? $\phi$ $\phi|x$ $\phi|x$ $\phi$ $x$ $\phi|x$

Par exemple, on pourrait essayer d'ajouter à chaque clause un littéral choisi au hasard dans la solution, qui ne se trouve pas déjà dans la clause. Cela garantira que est une solution. $x$

Ou est-ce sans espoir, conduisant à un algorithme rapide pour trouver la solution "cachée", dans le sens de l'article récent suivant?

Uriel Feige et Dorit Ron, Trouver des cliques cachées en temps linéaire , DMTCS proc. AM, 2010, 189-204.

Je suis au courant de la discussion de Cook et Mitchell et des travaux auxquels ils font référence. Cependant, je n'ai rien trouvé sur ce qui arrive à la structure d'une formule quand on essaie d'y incorporer explicitement une affectation satisfaisante. S'il s'agit de folklore, les pointeurs seraient les bienvenus!

Stephen A. Cook et David G. Mitchell, Finding Hard Instances of the Satisfiability Problem: A Survey , DIMACS Series in Discrete Mathematics and Theoretical Computer Science 35 1–17, AMS, ISBN 0-8218-0479-0, 1997. ( PS )

cc.complexity-theory sat hard-instances András Salamon
la source

Réponses:

$\varphi$ $\varphi \vee \psi_x$ $\psi_x$ $x$ $f:\{0,1\}^n\rightarrow \{0,1\}^n$ $x$ $y=f(x)$ $y$ $x$ $x$ $f$ $x$ $x$

Boaz Barak
la source

ϕ \lor ψ_{x}

$\phi \lor \psi_x$

ϕ

$\phi$

ψ_{x}

$\psi_x$

$\frac{m}{n}> 4.3$

$x$ $n$ $m$ $k$ $p = \frac{1}{2}$ $x$ $\phi|x$ $\phi$ $\phi|x$ $x$ $l$ $l$ $\phi$ $\phi|x$ $\phi$ $\phi|x$

$\phi|x$ $\phi$

$\phi$ $x$

$\phi$ $x$ $x$
$m_x$ $m_x$ $x$ $x$

$x$ $x$ $x$

Giorgio Camerani
la source

Merci pour les commentaires, j'accepte que l'espace de la solution soit modifié. Comme indiqué dans la question, je veux savoir s'il existe un moyen de modifier la formule pour masquer une solution. L'ajout des littéraux à chaque clause est considéré comme une preuve d'existence que l'on peut ajouter la solution à la formule. Je ne voulais pas suggérer que c'est la seule, la meilleure ou même une bonne méthode.

András Salamon

x

$x$

ϕ | x

$\phi|x$

ϕ

$\phi$

x

$x$

Idéalement, on veut une méthode calculable par polytime qui ne change pas trop l'espace de la solution ...

András Salamon

n^{3 \log n}

$n^{3\log\ n}$

3 \log n

$3 \log n$

n

$n$

2 n

$2n$

n

$n$

3 \log n

$3\log n$

La meilleure façon de générer des instances dures de problèmes NP complets que je connaisse est d'utiliser le mappage Cook pour réduire les instances soigneusement sélectionnées de certains autres problèmes NP durs (tels que le problème de logarithme discret ou la factorisation entière) en SAT. Ce sont les mêmes "problèmes difficiles" qui sont utilisés par les mathématiciens pour assurer la sécurité cryptographique dans des protocoles tels que RSA et Diffie-Hellman.

Philip White
la source

Références, s'il vous plaît?

gphilip

Je ne sais pas pourquoi le downvote pour cette réponse. celui qui l'a fait devrait expliquer.

Suresh Venkat