Monotone 3-SAT è esattamente 3 variabili distinte intraparabili?

Question

Ho dato la seguente variazione SAT:

.

Data una formula F in CNF in cui ogni clausola C ha esattamente 3 distinti letterali e per ciascuna C in f o tutti i letterali sono positivi o tutti i letterali sono negati. Esempio:

.

$ f= (x_1 \ vee x_2 \ vee x_4) \ wedge (\ neg x_2 \ vee \ neg x_3 \ vee \ neg x_3 \ vee \ neg x_4) \ wedge (x_3 \ vee x_4 \ vee x_5) $

.

Questa variazione di Sat Tractable?

I miei risultati finora:

Sospetto che il problema sia np-completo e quindi non trattato. Quindi vorrei eseguire una riduzione poli-riduzione da 3 stelle alla variazione sopra descritta.

Una formula arbitraria a 3 satelliti può essere convertita in monotone 3-SAT.

Prendi l'esempio seguente:

$ c_1= (x_1 \ vee x_2 \ vee \ neg x_3) $ e definisci $ z_3 $ di $ \ neg x_3 \ leftrightarrow z_3 $ e $ x_3 \ leftrightarrow \ neg z_3 $ che è equivalente a $ (x_3 \ vee z_3) \ wedge (\ neg x_3 \ vee \ neg z_3) $ .

Da che otteniamo la forma monotono di $ c_1 $ per

$ (x_1 \ vee x_2 \ vee \ neg x_3) \ leftrightarrow (x_1 \ vee x_2 \ vee z_3) \ wedge (x_3 \ vee z_3) \ wedge (\ neg x_3 \ Vee \ Neg z_3) $

Applicando questa trasformazione a tutte le clausole ottenendo una formula monotonale a 3 satelliti che è altrettanto soddisfaggiabile.

La mia riduzione produce ulteriori 2 clausole con 2 letterali per ogni clausola non monotono, ma come ottengo solo clausole monotoni con esattamente 3 distinti letterali?

Answer 1

Proverò a rispondere ora della mia domanda e sarebbe contento di alcuni feed back per quanto riguarda la corectezza.

Come nella domanda sopra discussa e sottolineata da Kyle Jones possiamo ridurre le formule arbitrarie a 3 satelliti a formule a 3 satelliti monotoni.

ad esempio una clausola $ c= (x_1 \ vee x_2 \ vee \ neg x_3) $ può essere convertito in $ C '(x_1 \ vee x_2 \ vee z_3) \ wedge (z_3 \ vee x_3) \ wedge (\ neg z_3 \ vee \ neg x_3) $ . Si può verificare se $ c $ è soddisfavole $ c '$ è anche soddisfavole e se $ c $ non è soddisfacente $ c '$ non è anche soddisfavole.

Il passo successivo è convertire tutte le clausole con meno di 3 letterali alle clausole con esattamente 3 distinti letterali.

Pertanto prendere ad esempio $ c_1= (x_1 \ vee x_2) $ e trasformarlo in $ c_1 '= ( x_1 \ vee x_2 \ vee y_1) \ wedge (x_1 \ vee x_2 \ vee y_2) \ wedge (x_1 \ vee x_2 \ vee y_3) \ wedge (\ neg y_1 \ vee \ neg y_2 \ vee \ neg y_2 \ vee \ neg y_3) $ quindi di nuovo se $ c_1 $ è soddisfacente $ c_1 '$ è anche soddisfatta e se $ c_1 $ non è soddisfavole $ c_1 '$ non è anche soddisfacente. Lo stesso può essere fatto per la custodia negativa ie $ c_2= (\ neg x_1 \ vee \ neg x_2) $ può essere trasformato in $ C_2 '= (\ neg x_1 \ vee \ neg x_2 \ vee \ neg u_1) \ wedge (\ neg x_1 \ vee \ neg x_2 \ vee \ neg x_2 \ vee \ neg u_2) \ wedge (\ neg x_1 \ vee \ neg x_2 \ Vee \ Neg u_3) \ wedge (u_1 \ vee u_2 \ vee u_3) $

Applicando le due trasformazioni si possono convertire un'istanza arbitraria a 3 satelliti in un'istanza monotonale 3-SAT con esattamente 3 distinti letterali. Come si può vedere facilmente sopra le trasformazioni hanno complessità polinomiale. Pertanto, dal momento che 3-sat è NP-HARD la riduzione ASWELL deve essere np-hard.