Complessità di casi specifici di max2sat

Question

So che Max2sat è NP-Completa in generale ma mi chiedo se sono noti certi casi limitati in P. certamente le lingue

$ l_k:=\ {\ phi \, | \, \ phi \, \ text {è un'istanza di 2sat che ha un incarico che soddisfa almeno i clausole K.} \ \ } $

può essere risolto in $ o (n ^ k) $ attraverso la ricerca della forza bruta poiché per ogni lingua $ k $ è fisso. Tuttavia, mi chiedo il caso quando viene specificata una frazione delle clausole. Qualsiasi frazione produce un problema rigido NP? In particolare mi sto chiedendo il caso di soddisfare almeno la metà delle clausole di un'istanza 2SAT.

La riduzione che ho visto da 3sat a max2sat costruisce 10 clausole da ogni clausola in 3sat tale da tali da queste dieci, esattamente 7 sono soddisfatte quando la clausola originale 3sat è soddisfatta e al massimo 6 sono soddisfatte quando la clausola originale non è soddisfatta . Quindi in questa riduzione la frazione di $ 7/10 $ funziona ma $ 1/2 $ non è perché la verità insoddisfacente Le assegnazioni di un'istanza 3SAT possono ancora produrre un'istanza di 2sat che ha un incarico che soddisfa più della metà delle clausole. Ho pensato ad un'altra costruzione o aggiungere clausole extra a un'istanza di 2sat ma non ho avuto successo finora.

Answer 1

Puoi sempre soddisfare almeno la metà delle clausole: per ogni variabile $ x $ , trova il numero di clausole che contengono $ x $ e il numero di clausole che contengono $ \ lnot x $ . Seleziona quello che soddisfa la maggior parte delle clausole. Rimuovere le clausole contenenti $ x $ e $ \ lnot x $ . Ripeti per altre variabili.

Dal momento che per ogni $ x $ Soddisfare almeno la metà delle clausole rimosse, soddisfiamo la metà delle clausole in generale.

D'altra parte, è anche stretto: let $ \ alfa> \ frac 12 $ essere la frazione di clausole per le quali possiamo dare una risposta. Let $ \ beta> \ frac 12 $ Sii la frazione massima delle clausole che possiamo soddisfare in una clausola specifica. Quindi possiamo aggiungere clausole in modo che $ \ beta $ (per la nuova clausola) diventa clausola arbitraria a $ \ alfa $ < / SPAN>:

.
• se $ \ beta <\ alfa $ , quindi possiamo aggiungere clausole $ (x_i \ lor \ lnot x_i) $ , fino a $ \ beta> \ alfa $ (poiché queste clausole sono sempre true, $ \ beta $ Aumenta).
• se $ \ beta> \ alfa $ , possiamo aggiungere clausole $ (x_i) $ e $ (\ lnot x_i) $ , fino a $ \ beta <\ alfa $ (poiché esattamente la metà delle clausole è vero, $ \ beta $ diminuisce).

Non ho controllato, ma per ottenere $ o (\ frac 1m) $ differenza (cioè per trovare il numero esatto di clausole), penso che sia sufficiente Per aggiungere $ o (m) $ clausole. In altre parole, se possiamo risolvere per qualche $ \ alfa> \ frac 12 $ , possiamo controllare qualsiasi classe $ \ beta $ se $ \ beta $ frazione di clausole può essere soddisfatta, e quindi possiamo risolvere MAX2SAT in tempo polinomiale.