Trouvez

9

Soit le langage de toutes les formules -CNF , de sorte qu'au moins des clauses de puissent être satisfaites. $L_\epsilon$ $2$ $\varphi$ $(\frac{1}{2}+\epsilon)$ $\varphi$

Je dois prouver qu'il existe st is -hard for any . $\epsilon'$ $L_\epsilon$ $\mathsf{NP}$ $\epsilon<\epsilon'$

Nous savons que peut être approximativement au précédent des clauses d'une réduction . Comment dois-je résoudre celui-ci? $\text{Max}2\text{Sat}$ $\frac{55}{56}$ $\text{Max}3\text{Sat}$

complexity-theory satisfiability approximation Joni
la source

8

Dans son célèbre article, Håstad montre qu'il est difficile pour NP d'approcher MAX2SAT mieux que . Cela signifie probablement qu'il est difficile de distinguer NP des instances qui sont satisfaisables et des instances qui sont satisfaisables, pour certains $21/22$ $\leq \alpha$ $\geq (22/21) \alpha$ . Imaginons maintenant rembourrage une instancesorte qu'il devient un fractionune nouvelle instance, le reste dequi est exactement -satisfiable (dire qu'il est constitué de groupes d'articles de la forme ). Les chiffres sont maintenant $\alpha \geq 1/2$ $p$ $1/2$ $a \land \lnot a$ et . Ce dernier chiffre peut être aussi proche de que nous voulons. $1/2 + p (\alpha - 1/2)$ $1/2 + p((22/21)\alpha - 1/2)$ $1/2$

Yuval Filmus
la source

Votre méthode fonctionne-t-elle lorsque ε est un nombre réel arbitraire (mais suffisamment petit)? Je ne peux pas comprendre comment choisir le nombre approprié de clauses à utiliser pour le remplissage, sauf si je suppose quelque chose à propos de ε. (Notez que ε ne fait pas partie de l'entrée, et donc il est bien défini de considérer le nombre réel ε.)

Tsuyoshi Ito

Voilà où l'écart entre

et

pourrait être utile. En supposant que

est rationnel, prenez un

rationnel , et vous devriez bien faire.

1 / 2 + p (α - 1 / 2)

$1/2+p(\alpha-1/2)$

1 / 2 + p ((22 / 21) α - 1 / 2)

$1/2+p((22/21)\alpha-1/2)$

α

$\alpha$

p

$p$

Yuval Filmus

Aha, d'une manière ou d'une autre, je pensais que cette méthode ne fonctionnait pas lorsque je l'ai essayée en premier, mais maintenant je vois comment cela fonctionne. Merci!

Tsuyoshi Ito

5

Si vous savez que ε est un nombre rationnel, vous n'avez pas besoin d'inapproximabilité pour Max-2-SAT pour prouver votre déclaration. Une preuve typique de la dureté NP de Max-2-SAT (par exemple, celle du manuel Computational Complexity de Papadimitriou) prouve en fait l'exhaustivité NP de L _1/5 . Pour prouver la dureté NP de L _ε pour des nombres rationnels positifs ε <1/5, nous pouvons réduire L _1/5 à L _ε comme suit: étant donné une formule 2CNF φ (une instance pour L _1/5 ), soit m soit le nombre de clauses qu'il contient. Soit r ets être des entiers positifs tels que (1 / 5− ε ) mr = 2 ε s est vrai. Construisez ensuite une formule 2CNF (une instance de L _ε ) en répétant φ pour r fois et en ajoutant s paires de clauses contradictoires. Un calcul simple montre qu'il s'agit bien d'une réduction de L _1/5 à L _ε .

Cette réduction ne fonctionne clairement que si ε est rationnel, car sinon r et s ne peuvent pas être pris comme entiers. Le cas général où ε n'est pas nécessairement rationnel semble nécessiter une inapproximabilité, comme l'a écrit Yuval Filmus dans sa réponse.

Tsuyoshi Ito
la source

Trouvez

Réponses: