Preuve que positif-3-sat est dans la complexité de classe P

Question

J'ai la langue suivante:

$$ text {positif-3-sat} = { Langle phi Rangle mid phi tex 3 littéraux et dans lesquels aucune variable n'apparaît annulée} }. $$

---

Progrès jusqu'à présent:

Ma préoccupation est que je n'ai pas compris la tâche. J'ai proposé ce que je pense être une preuve (presque triviale).

Pour montrer que la langue est dans P, mon approche consiste à fournir un algorithme déterministe qui peut décider du problème en temps polynomial.

Par définition, $ text {positif-3-sat} $ doit comprendre un nombre arbitrairement long de conjonctions de clauses de la forme $ ( lambda_1 lor lambda_2 lor lambda_3) $. Chaque clause est trivialement satisfait dans le cas qu'une valeur de vérité de True est attribuée à l'une des clauses $ lambda_1, lambda_2, lambda_3 $. Sur cette base, chaque clause contenant 3 littéraux peut être décidée dans $ O (3) $ pas, $ équiv o (1) $.

Si nous faisons l'hypothèse que le langage est contraint de ne contenir qu'un nombre fini de $ n $ Clauses, alors nous pouvons dire que la satisfabilité de la langue peut être décidée dans $ O (n) équiv o (n ^ 1) $ pas.

Ainsi, $ text {positif-3-sat} $ Peut être décidé par un algorithme déterministe en temps polynomial.

Ainsi, $ text {positif-3-sat} dans $ NP.