La complessità di varianti 3SAT

Question

Questa domanda è motivata dal mio risposta ad un'altra domanda in cui ho dichiarato il fatto che sia betweeness e Non problemi -Betweeness sono $ NP $ -Complete. Nel primo problema esiste un ordine totale tale che il vincolo betweeness di ogni tripla è eseguita mentre il problema più tardi c'è un ordine totale tale che il vincolo betweeness di ogni tripla è violata.

Qual è la complessità dei seguenti 3SAT varianti:?

3SAT_1 = {($ \ phi $): $ \ phi $ ha un incarico che fa di ogni clausola di false}

3SAT_2 = {($ \ phi $): $ \ phi $ ha un'assegnazione tale che esattamente la metà delle clausole sono vere e l'altra metà è falso}

Answer 1

3SAT_1 è facile, e una variante di 3SAT_2 è NP-completo. La mia ipotesi è che 3SAT_2 è anche NP-completo. Aggiornamento:. La mia ipotesi è dimostrato al di sotto

Sia $ C = x \ lor y \ lor z $ essere una clausola. Quindi $ \ lnot C = \ lnot x \ terra \ lnot y \ terra \ lnot z $. Un'assegnazione rende ogni clausola di $ \ phi $ false se fa tutte le loro negazioni vero. La congiunzione della negazione di tutte le clausole è solo un grande congiunzione. Una congiunzione è soddisfacibile se e solo se non contiene una variabile e la sua negazione. Così 3SAT_1 è in P (in realtà è in AC $ ^ 0 $).

La variante di 3SAT_2 chiede se $ \ phi $ ha un'assegnazione che fa esattamente $ 8/9 $ delle clausole vere. Questo è chiaramente in NP. Per ridurre 3SAT a questa variante, prendere la formula $ \ $ phi, e per ogni clausola di $ C $ a $ \ phi $ aggiungere gli otto clausole $$ (x_C \ lor y_C \ lor z_C) \ terra \ cdots \ terra (\ lnot x_C \ lor \ lnot y_C \ lor \ lnot z_C). $$ In ogni incarico, esattamente sette di questi sono corretti. In totale ci sono $ 9 | \ phi | $ clausole. Dei $ 8 | \ phi | $ che abbiamo aggiunto, esattamente $ 7 | \ phi | $ sono sempre corrette. Quindi $ \ phi $ è soddisfacibile se e solo se la nuova formula in grado di soddisfare esattamente $ 8 | \ phi |. $ Vincoli, che sono $ 8/9 $ delle sue clausole

Aggiornamento: Qui è una riduzione dal 3SAT a 3SAT_2 sé. Data una formula $ \ $ phi, considerare due casi. Il primo caso è quando siamo in grado di falsificare tutte le clausole di $ \ phi $ in una sola volta. Come mostrato sopra, in questo caso ogni variabile appare solo positivo o solo negativamente, e quindi impostando in modo appropriato, la formula è soddisfacibile. In caso contrario, aggiungere $ | \ phi | $ clausole del modulo $ x \ lor y \ lor z $, dove $ x, y, z $ sono nuove variabili. In ogni incarico o tutti questi sono soddisfatti, o non tutti sono soddisfatti. Dal momento che le clausole originali non possono essere tutti falsificati in una volta (per ipotesi), la nuova formula può essere mezza soddisfatta se e solo se l'originale è soddisfacibile.