Théorème de dichotomie de Schaeffer

Bound

Bonjour.

J'ai un peu de mal à comprendre le théorème de dichotomie de Schaeffer.

Nous avons le problème A sous-ensemble de 3-SAT respectant les 2 contraintes suivantes:

- chaque clause n'est satisfaite que par un seul littéral comme dans One-in-3SAT.

- aucune des clauses ne contient 3 littéraux négatifs : par exemple,  $\overline{x_{1}} \vee \overline{x_{2}} \vee \overline{x_{3}}$ n'est dans aucune des clauses.

Est-ce que le théorème de Schaeffer dit que ce problème A est dans P, NP-Complet ou ni l'un ni l'autre?

Personnellement, je pense que ce problème est NP-Complet mais je ne suis pas sûr.

Merci d'avance pour vos réponses.