Complessità del tempo di solutori satellitati all'avanguardia rispetto alla lunghezza della formula

Question

Sto imparando a DPLL e CDCL SAT SOLVERS, e so che hanno la complessità del tempo esponenziale al numero di variabili.

Se non sono sbagliato, uno dei motivi per cui più credo P non uguale a NP è che non esiste un algoritmo polinomiale per Sat nonostante uno sforzo tremendo dei matematici e degli informatori. Tuttavia, il problema P VS NP si prende cura solo della complessità del tempo rispetto alla lunghezza della formula, non sul numero di variabili.

Se questi solutori SAT all'avanguardia sono stati eseguiti su formule 3CNF, quindi una complessità del tempo esponenziale al numero di variabili implica una complessità del tempo esponenziale alla lunghezza del 3CNF.

Tuttavia, se fossero eseguiti su CNF arbitrari, la cui lunghezza può essere esponenziale al numero di variabili, quindi una complessità del tempo esponenziale al numero di variabili non implicherebbe necessariamente una complessità del tempo esponenziale alla lunghezza del CNF.

Pertanto, è una domanda correlata, sono questi solutori SAT correnti su 3CNF o CNF durante la misurazione della complessità del tempo?

Answer 1

Per 3SAT, il numero di variabili è polinomia relativo al numero di clausole. (Vedi la fine per la giustificazione.)

Di conseguenza, qualsiasi algoritmo per 3sat il cui tempo di esecuzione è polinomiale nel numero di clausole sarebbe anche polinomiale nel numero di variabili; E qualsiasi algoritmo per 3sat il cui tempo di esecuzione è polinomiale nel numero di variabili sarebbe anche polinomiale nel numero di clausole.

È noto che esiste un algoritmo poligomiale per 3sat, se e solo se c'è un algoritmo polinomiale per sab, se e solo se c'è un algoritmo poligomiale per circuit (ad esempio, per formule) . Inoltre, nonostante i decenni di lavoro su SOLL SOLVERS, nessuno conosce alcun algoritmo per 3sat che corre in tempo polinomiale (o infatti in meno del tempo esponenziale nel peggiore dei casi). Potresti prendere questo come prova che non esiste un algoritmo polinomiale per 3sat; Il che implica che non esiste un algoritmo polinomiale per satellitare o circuito, e implica anche che p!= np.

---

.

Motivazione: Let $ N $ Denota il numero di variabili e $ m $ Il numero di clausole . Abbiamo $ n \ le 3m $ (una variabile che non appare in nessuna clausola può essere ignorata) e $ m \ le 8n ^ 3 $ (ogni clausola ha tre livelli e puoi ignorare le clausole ripetute). Ne consegue che $ N / 3 \ Le m \ le 8n ^ 3 $ e $ \ sqrt [3] {m / 8} \ Le n \ le 3m $ , cioè, ciascuno è legato polinomiamente all'altro.

---

.

Vedo che hai rivisto la tua domanda. Ciò chiarisce che penso che tu abbia un equivoco. Parli di "Esegui [Ning] [un solver satellitare] sulle formule booleane arbitrarie". Tuttavia, non è possibile eseguire un risolutore satellitare su una formula booleana arbitraria. I solvisti satelliti funzionano solo sulle formule CNF.

Tuttavia, sappiamo che qualsiasi formula booleana può essere convertita in una formula di dimensioni CNF equatisficable nella maggior parte dei polinomiali delle dimensioni della formula e viceversa. Se avessi un algoritmo che potrebbe testare la soddisfazione delle formule booleane arbitrarie in tempo polinomiale nella dimensione della formula, quindi seguirebbe che si dispone di un algoritmo che potrebbe testare la soddisfazione delle formule 3CNF in tempo polinomiale nella dimensione della formula (ogni La formula 3CNF è una formula booleana), e quindi un algoritmo che potrebbe testare la soddisfazione delle formule 3CNF in tempo polinomiale nel numero di variabili - che contraddice le prove disponibili. Quindi, se ritieni che non vi sia un algoritmo per risolvere il 3 secondario in tempo polinomiale nel numero di variabili, allora dovresti anche ritenere che non vi sia un algoritmo per testare la soddisfazione delle formule booleane arbitrarie in tempo polinomiale nella dimensione della formula. < / P >.