È trovare la soluzione a un sistema di equazioni 2SAT separate da o (modulo DNF) in NP

Question

Voglio sapere se la ricerca della soluzione a un numero specifico di equazioni 2SAT semettate da o gate (modulo DNF come di seguito) è in P o NP.

L'equazione ha in totale N Variabili e ogni clausola è un'equazione di 2SAT in sé in un sottoinsieme di variabili da 1 a n. Esempio:

f= [(x1 || x2) && (! x2 || x3) && (x3 || x4)] ||[(x2 || x5) && (x3 || x6) && (! x4 ||! x6)] ||....

L'equazione F è un DNF di equazioni di 2SAT, che ha detto m clausole.Sta trovando una soluzione a questo in NP?Se sì, come?

Inoltre, in particolare voglio anche sapere se la ricerca di casi false di equazione F è in P o NP pure.

Answer 1

.
• In primo luogo, fammi notare che il titolo della domanda è un po 'fuorviante, perché $ p $ è un sottoinsieme di $ NP $ . Vedi anche il commento di Yuval Filmus. Suppongo cosa tu previsto per chiedere è se è in $ P $ o in $ NP \ setmino p $ .
• Inoltre, il nome "DNF" si riferisce specificamente a una disgiunzione di elementari , non una disgiunzione di funzioni arbitrarie. Quello che stai descrivendo non è un DNF, ma una disgiunzione di CNFS.

Con quello fuori di mezzo, ecco la mia risposta.

---

.

.

1. Per soddisfare una disgiunzione di 2-cnfs, tutto ciò di cui hai bisogno è soddisfare uno di loro. Quindi, se si applica l'algoritmo a 2 satelliti al primo dei cnfs e ottieni un "sì", quindi la risposta a tutto il problema è "sì". Altrimenti, vai avanti verso il secondo, e così via. Non dovrebbe richiedere molto tempo, dal momento che hai solo m di loro. Se nessuno di loro può essere soddisfatto individualmente, cioè sono tutti zeri costanti, quindi ovviamente l'intera cosa è uno zero costante.

   Quindi la risposta alla prima parte è: il problema è in P, con il seguente algoritmo decisionale:

   Per ogni 2-CNF, applicare l'algoritmo "normale" a 2 satelliti (la regola di risoluzione) per determinare se è soddisfatta o meno. Se "sì", restituisci "sì". Se ne hai attraversato tutti senza trovare un "sì", quindi restituire "no".

---

.

2. Ora, trovando i casi "falsi" di quella formula (noto anche come il problema della tautologia) è interamente un'altra domanda. Per una cosa, la tautologia per ORS di ANDS di ORS è equivalente alla soddisfattiva per es di ORS di ANDS, dalla regola di De Morgan. Ma questo è solo un caso più generale di un problema SAT già generale, non è vero?

   Considera cosa succede quando limita la serie di possibili formule a quelle in cui ogni disgiunzione di due elementi è davvero solo un elemento, ripetuto. Quindi è una formula come $$ F= [(x_1 \ vee x_1) \ & (\ neg x_2 \ vee \ neg x_2) \ & (x_3 \ vee x_3)] \ vee [(x_2 \ vee x_2) \ & (x_4 \ vee x_4) \ & ( x_5 \ vee x_5)]] \ vee ... $$ che è equivalente a $$ F= [x_1 \ & \ neg x_2 \ & x_3] \ vee [x_2 \ & x_4 \ & x_5] \ vee ... $$ che è solo un DNF normale. Dopo la trasformazione di De Morgan, ottieni un normale CNF, la cui soddisfabilità è nota per essere np-hard. Pertanto, qualsiasi problema che include questo come sottoinsieme sarà anche almeno np-hard.

   Ovviamente, il problema in questione non sarà esterno np, perché è ancora polinomiamente verificabile. Quindi la risposta alla tua seconda domanda è "in NP, ma non in P".