È possibile risolvere 4SAT in tempo polinomiale?[Chiuso]

Question

Lo so e lo ammetto lungo, ma per favore leggilo lentamente e capisci tutto.

Penso che questa sia una delle domande più interessanti che l’informatica abbia mai posto.

Io facciono aspettatevi risposte rapide.Prenditi il ​​tuo tempo per leggere lentamente e per capire tutto.Posso aspettare.Io facciono fretta.

In 1SAT, la macchina di turing deve determinare se una formula 1CNF è soddisfacibile o meno, dove la formula 1CNF è una congiunzione di clausole, dove ciascuna clausola è solo 1 letterale, che è una variabile positiva o negativa.

È noto che questo problema si trova in $\Bbb{P}$, la classe di tutti i problemi risolvibili in tempo polinomiale, ma è non NP-Problema completo.

In 2SAT, la macchina di turing deve determinare se una formula 2CNF è soddisfacibile o meno, dove la formula 2CNF è una congiunzione di clausole, dove ciascuna clausola è una disgiunzione di al massimo 2 letterali, dove ogni letterale è una variabile positiva o negativa.

È interessante notare che se si trasforma ogni disgiunzione in congiunzione nella formula 2CNF data, si ottiene la formula 1CNF e il problema diventa 1SAT, che è già noto essere in $\Bbb{P}$ e se questa formula è soddisfacibile, allora anche la formula 2CNF originale è soddisfacibile, ma se la formula 1CNF data è insoddisfacibile, questo è non significa necessariamente che anche la formula originale 2CNF è insoddisfacente.

Poiché nella formula 2CNF originale è presente una disgiunzione tra ciascuna coppia di valori letterali, anziché una congiunzione, è possibile consentire che uno dei valori letterali sia falso nell'input, ma non entrambi.Quindi, se lo è non È possibile impostare entrambi i valori letterali su vero nella stessa clausola in modo che la formula 2CNF risulti vera, quindi l'algoritmo o la macchina di turing deve decidere quale di essi dovrebbe essere falso, quindi la formula 2CNF risulta vera.

In effetti questo è un problema decisionale, ma è noto che si trova anche in $\Bbb{P}$, perché è possibile semplicemente costruire un grafico delle implicazioni e trovare un cerchio di contraddizione per dimostrare che la formula 2CNF è insoddisfacente.Se non viene trovato alcun cerchio di contraddizione, la formula 2CNF è soddisfacibile.

Quindi, anche se da 1SAT a 2SAT il problema diventa un problema decisionale (il cui letterale in ciascuna clausola dovrebbe essere impostato su falso), la macchina di turing può comunque risolverlo deterministicamente in tempo polinomiale, ma sfortunatamente 2SAT lo èno Anche NP-completo.

In 4SAT, la macchina di turing deve determinare se una formula 4CNF è soddisfacibile o meno, dove la formula 4CNF è una congiunzione di clausole, dove ciascuna clausola è una disgiunzione di al massimo 4 letterali, dove ogni letterale è una variabile positiva o negativa.

È interessante notare che se si trasforma ogni disgiunzione in congiunzione nella formula 4CNF data, si ottiene la formula 1CNF e il problema diventa 1SAT, che è già noto essere in $\Bbb{P}$, e se la formula 1CNF data è soddisfacente, allora anche la formula originale 4CNF è soddisfacibile, ma se la formula 1CNF è insoddisfacibile, lo fano significa necessariamente che anche la formula 4CNF è insoddisfacente.

Quindi in quel caso l'algoritmo o la macchina di turing dovrà tornare alla formula originale 4CNF e in ciascuna clausola trasformare la disgiunzione centrale in congiunzione, cioèSe

(l₁ ∨ l₂ ∨ l₃ ∨ l₄) è una clausola arbitraria dalla formula arbitraria 4CNF, allora il significato di trasformare la disgiunzione centrale in congiunzione è trasformare quella clausola arbitraria in (l₁ ∨ l₂) ∧ (l₃ ∨ l₄).

Se lo fai, ottieni la formula 2CNF e il problema diventa 2SAT, che è anche noto essere in $\Bbb{P}$, e se questa formula 2CNF è soddisfacibile allora anche la formula originale 4CNF è soddisfacibile, ma se la formula 2CNF è unsoddisfacente, allora lo fano significa necessariamente che la formula originale 4CNF lo è unanch'esso soddisfacibile, perché nella formula originale 4CNF c'è disgiunzione tra le due coppie di letterali, ma non congiunzione, quindi la macchina di turing fano dobbiamo trovare un input, quindi entrambe le coppie di valori letterali valgono vero, ma è sufficiente che uno di loro valga vero e l'altro valga falso.

Come puoi vedere, 4SAT è un problema decisionale come lo è 2SAT, quale coppia di valori letterali dovrebbe essere valutata come falsa in ciascuna clausola e quale no, ad es.dovrebbe essere valutato come vero.

Questa domanda è simile al precedente, quando la macchina di Turing deve risolvere 2SAT e deve determinare quale letterale dovrebbe essere falso in ciascuna clausola, invece della coppia, ma la macchina di Turing può risolvere 2SAT deterministicamente in tempo polinomiale costruendo il grafico delle implicazioni e cercando di trovare contraddizioni circle, quindi non deve determinare quale letterale dovrebbe essere falsa in ciascuna clausola.

Lo stesso qui con 4SAT, non penso che la macchina di turing debba decidere quale coppia di valori letterali dovrebbe valutare come falsa in ciascuna clausola.

Credo che esista un metodo che la macchina di Turing può eseguire in modo deterministico per risolvere 4SAT in tempo polinomiale, forse simile al metodo per risolvere 2SAT in tempo polinomiale.

Non penso che 4SAT sia un problema così difficile.

Quando si trasforma la disgiunzione centrale in congiunzione in ciascuna clausola, si ottiene la formula 2CNF e la macchina di Turing può costruire in modo deterministico il grafico delle implicazioni per essa in tempo polinomiale.

Se la macchina Turing non trova il cerchio di contraddizione, la formula 4CNF originale è soddisfacente.

Ma se la macchina di Turing trovasse un cerchio di contraddizione, allora la macchina di Turing dovrà modificare il grafico, quindi non ci sarà alcun cerchio di contraddizione nel grafico.

Se esiste un modo per apportare questa modifica, in modo che non vi sia alcun cerchio di contraddizione nel grafico, allora la formula 4CNF è soddisfacente, anche se la formula 2CNF data non lo è.

Ma se la macchina di Turing dimostra che non esiste tale modifica al grafico delle implicazioni, per cui ogni cerchio di contraddizioni può essere risolto, allora la formula originale 4CNF è insoddisfacente.

In ciascuna clausola 4CNF, decidere quale coppia di valori letterali dovrebbe essere vera e quale dovrebbe essere falsa significa decidere quale arco dovrebbe essere nel grafico delle implicazioni e quale arco non dovrebbe essere nel grafico delle implicazioni.

Se la macchina di Turing presuppone che tutte le coppie possano essere vere, allora tutti gli archi sono nel grafico, ma se trova un cerchio di contraddizione, allora decidere in ciascuna clausola quale coppia di letterali dovrebbe essere falsa significa decidere da quale arco dovrebbe essere rimosso il grafico delle implicazioni, quindi non c’è contraddizione.

È interessante notare che passando da 1SAT a 2SAT, il problema diventa un problema decisionale, ma sia 1SAT che 2SAT lo sonono np-completo, anche se entrambi possono essere risolti in tempo polinomiale.

Quando si passa da 2SAT a 4SAT, il problema diventa nuovamente un problema decisionale, ma 4SAT è np-completo, a differenza di 2SAT, perché il problema di soddisfacibilità booleana, che è stato il primo problema a essere dimostrato np-completo nell'articolo di Cook e Karp, può essere ridotto a 4SAT in tempo polinomiale.

La mia domanda interessante è: la macchina di Turing può risolvere 4SAT in modo deterministico in tempo polinomiale come può in 2SAT?

Non penso che la macchina di turing debba davvero decidere in ogni clausola quale bordo dovrebbe essere rimosso dal grafico delle implicazioni poiché in 2SAT la macchina di turing non deve decidere quale letterale dovrebbe essere falso in ciascuna clausola.

Penso che dovrebbe esserci un metodo molto efficiente che la macchina di Turing può utilizzare per risolvere l'alleato deterministico 4SAT in tempo polinomiale come in 2SAT.

Cosa ne pensi?

Qual è la tua opinione?