Question

Est-ce que le théorème de la dichotomie de Schaefer établit qu'une clause générale à 3-SAT ne peut pas être transformée en un ensemble équivalent de clauses 2-SAT / Hornsat / Affine (en utilisant des variables auxiliaires) ou simplement que cela serait très improbable en ce que cela impliquerait P = NP? Je demande parce que je sais qu'il existe certains types de problèmes impliquant des clauses de 3 lits qui peuvent être transformées en clauses équivalentes à 2 SAT / Hornsat. Je pense spécifiquement à 2-ou-3 SAT qui peut être résolu par des clauses 2-SAT / ANTISATAT ou 1-OR-3 SAT qui peuvent être résolues à l'aide de clauses affines.

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top