Est-il possible de résoudre 3sat en O (n ^ 24) Temps et O (1) Espace?

Question

Suppose que n est le nombre de variables de la formule 3CNF donnée (n≥3) et toutes les clauses de la formule 3CNF donnée sont différentes.

Cela signifie que pour chaque clause, chaque littéral peut être positif ou négatif et être l'un des n variables, donc le nombre d'options pour chaque littéral est 2n, mais chaque clause a exactement 3 littéraux, donc le nombre maximum de clauses différentes est 2n • 2n • 2n = (2n)³ = 8n³ = O (n³).

J'ai lu ici Cette formule 3CNF doit avoir au moins 8 clauses différentes dans la forme:

(x ∨ y ∨ z) ∧ (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z) ∧ (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z) ∧ (¬x ∨ y y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z)

être insatisfaisant.

Si cette petite formule 3CNF est incluse ou sous-ensemble d'une formule 3CNF plus grande, la formule 3CNF plus grande n'est pas satisfaisante à coup sûr, en raison de ce sous-ensemble.

Ainsi, l'algorithme doit rechercher ce sous-ensemble et si l'algorithme l'a trouvé, l'algorithme renvoie "la formule donnée n'est pas satisfaisable" en tant que sortie.

Et cela supposait être correct à coup sûr.

Mais que se passe-t-il si l'algorithmeNT trouver un tel sous-ensemble?

Cela signifie-t-il nécessairement que la formule 3CNF donnée est-elle ne pas ONUSatisfait, c'est-à-dire satisfaisant?

Parce que le sous-ensemble a exactement 8 clauses, l'algorithme doit itérer à travers tous les différents sous-ensembles de 8 clauses dans la formule 3CNF donnée.

Si la formule 3CNF donnée a m clauses, alors il devrait y avoir θ (m⁸) différents sous-ensembles de 8 clauses, mais si toutes les clauses sont différentes, alors m = o (n³), donc o ((n³)⁸) = O (n^3•8) = O (n²⁴)

Ainsi, le temps d'exécution de l'algorithme itérater à travers tous ces sous-ensembles et pour trouver le sous-ensemble insatisfaisable, s'il existe, prend θ (n²⁴) temps.

Pour ce faire, l'algorithme a besoin de 8 intérieurs pour les boucles, où chacun pour la boucle est à l'intérieur de l'autre, avec 8 variables itératives.

Parce que l'algorithme n'alloue aucune mémoire pendant le temps d'exécution, la complexité de l'espace de cet algorithme supposait être θ (1).

Faites-moi savoir si je me trompais et sur quoi, c'est-à-dire si je me trompe, alors pourquoi?

Pourquoi j'avais tort?

S'il vous plaît, expliquez.

Je veux apprendre des erreurs.

je pense que

C'est trop beau pour être vrai

et

Si c'est trop beau pour être vrai, quelque chose ne va pas.