Trova $ \ epsilon '$ s.t $ L_ \ epsilon $ è $ \ {mathsf NP} $ - difficile per qualsiasi \ epsilon <\ epsilon $' $

Question

Let $ L_ \ epsilon $ essere il linguaggio di tutti i 2 $ -CNF formule $ \ varphi $, in modo che almeno $ (\ frac {1} {2} + \ epsilon) $ di $ \ varphi $ s $ ' clausole possono essere soddisfatte.

Ho bisogno di dimostrare che esiste $ \ epsilon '$ s.t $ L_ \ epsilon $ è $ \ {mathsf NP} $ - difficile per qualsiasi $ \ epsilon <\ epsilon'. $

Sappiamo che $ \ text {max} 2 \ text {Sat} $ può essere approssimativa a $ \ frac {55} {56} $ precent delle clausole da un testo $ \ {max} 3 \ text {Sat } $ riduzione. Come devo risolvere questo?

Answer 1

Nel suo famoso articolo, Håstad mostra che è NP-difficile MAX2SAT approssimativa meglio di $ 21/22 $. Questo probabilmente significa che è è NP-difficile distinguere i casi che sono $ \ leq \ alpha $ satisfiable e le istanze che sono $ \ geq (22/21) \ alpha $ satisfiable, per qualche \ alpha \ geq mezzo $ $. Ora immaginate imbottitura un'istanza in modo che diventi un $ p $ -fraction di una nuova istanza, il resto che è esattamente $ 1/2 $ -satisfiable (dicono che è costituito da gruppi di clausole della forma $ a \ terra \ lnot un $). I numeri diventano ora $ 1/2 + p (\ alpha - 1/2) $ e $ 1/2 + p ((22/21) \ alpha - 1/2) $. Quest'ultimo numero può essere fatto come vicino a $ 1/2 $ come vogliamo.

Answer 2

Se si sa che e è un numero razionale, inapproximability quindi non è necessario per Max-2-SAT per dimostrare la sua dichiarazione. Una prova tipica della NP-difficile di Max-2-SAT (ad esempio, quella del libro di testo complessità computazionale di Papadimitriou) dimostra in realtà la NP-completezza del L < sub> 1/5 . Per dimostrare l'NP-difficile di L _e per numeri razionali positivi e <1/5, possiamo ridurre L _1/5 L _e come segue: data una formula 2CNF < i> f (un'istanza per L _1/5 ), lasciate m essere il numero di clausole in esso. Lasciate r e s essere numeri interi positivi tali che (1 / 5- e ) mr = 2 e s detiene. Poi costruire una formula 2CNF (un'istanza per L _e ) ripetendo f r volte e aggiungendo s coppie di clausole contraddittorie. Un semplice calcolo mostra che questa è davvero una riduzione da L _1/5 L _e .

Questa riduzione funziona chiaramente solo se e è razionale, perché altrimenti r e s non può essere presa come interi. Il caso generale in cui e non è necessariamente razionale sembra richiedere inapproximability, come Yuval Filmus ha scritto nella sua risposta.