Complexités temporelles des solveurs SAT à la pointe de la technologie en ce qui concerne la longueur de la formule

Question

J'apprends des solveurs DPLL et CDCL SAT, et je sais qu'ils ont une complexité de temps exponentielle au nombre de variables.

Si je ne me trompe pas, l'une des raisons pour lesquelles la plupart croient que P n'est pas égal à NP, c'est qu'il n'existe aucun algorithme de temps polynomial pour SAT malgré des efforts considérables des mathématiciens et des informaticiens. Cependant, le problème P vS NP ne se soucie que de la complexité de temps en ce qui concerne la longueur de la formule, pas le nombre de variables.

Si ces solvateurs SAT à la pointe de la technique ont été exécutés sur des formules 3CNF, une complexité de temps exponentielle au nombre de variables implique une complexité de temps exponentielle à la longueur du 3cnf.

Cependant, si elles étaient exécutées sur des CNF arbitraires, dont la longueur peut être exponentielle au nombre de variables, une complexité de temps exponentielle au nombre de variables n'impliquerait pas nécessairement une complexité de temps exponentielle à la longueur du CNF.

Ainsi, une question connexe est, ces solveurs SAT fonctionnent-ils sur 3CNF ou CNF tout en mesurant la complexité de temps?

Answer 1

Pour 3SAT, le nombre de variables est en polynomie liée au nombre de clauses. (Voir la fin pour la justification.)

Par conséquent, tout algorithme de 3SAT dont le temps de fonctionnement est polynomial dans le nombre de clauses serait également polynomial dans le nombre de variables; et tout algorithme de 3SAT dont le temps de fonctionnement est polynomial dans le nombre de variables serait également polynomial dans le nombre de clauses.

On sait qu'il existe un algorithme de temps polynomial pour 3SAT, si et uniquement s'il y a un algorithme de temps polynomial pour SAT, si et uniquement s'il y a un algorithme de temps polynomial pour circuitsat (par exemple, pour les formules) . En outre, malgré des décennies de travaux sur les solveurs SAT, personne ne connaît aucun algorithme pour 3SAT qui fonctionne dans du temps polynomial (ou en moins de temps exponentiel dans le pire des cas). Vous pouvez prendre cela comme preuve qu'il n'y a pas d'algorithme de temps polynomial pour 3SAT; qui implique qu'il n'y a pas d'algorithme de temps polynomial pour SAT ou CIRCUITSAT, non plus, et implique également que p!= np.

---

Justification: laissez $ n $ dénote le nombre de variables et $ m $ le nombre de clauses . Nous avons $ n \ le 3m $ (une variable qui n'apparaît pas dans une clause peut être ignorée) et M $ M \ LE 8N ^ 3 $ (chaque clause a trois littéraux et vous pouvez ignorer des clauses répétées). Il s'ensuit que $ n / 3 \ le m \ le 8n ^ 3 $ et $ \ sqrt [3] {m / 8} \ Le n \ le 3m $ , c'est-à-dire que chacun est lié polnoméal à l'autre.

---

Je vois que vous avez révisé votre question. Cela clarifie que je pense que vous avez une idée fausse. Vous parlez de «Run [Ning] [un solveur SAT] sur des formules booléennes arbitraires». Cependant, vous ne pouvez pas exécuter un solutionneur SAT sur une formule booléenne arbitraire. Les solveurs SAT ne fonctionnent que sur les formules CNF.

Cependant, nous savons que toute formule booléenne peut être convertie en une formule de taille CNF équiditative au plus polynôme de la taille de la formule, et inversement. Si vous aviez un algorithme susceptible de tester la satisfaction des formules booléennes arbitraires dans le temps polynôme de temps dans la taille de la formule, cela suivrait que vous avez un algorithme qui pourrait tester la satisfaction des formules 3CNF dans le temps polynomial dans la taille de la formule (chaque La formule 3CNF est une formule booléenne) et donc un algorithme susceptible de tester sa satisfaction des formules 3CNF dans le temps polynomial dans le nombre de variables - qui contredit les preuves disponibles. Donc, si vous croyez qu'il n'y a pas d'algorithme pour résoudre le polynôme de 3 sat dans le nombre de variables, vous devriez également croire qu'il n'y a pas d'algorithme pour tester la satisfaction des formules booléennes arbitraires dans le temps polynomial dans la taille de la formule. < / p>