Pergunta

Does Schaefer's dichotomy theorem establish that a general 3-sat clause cannot be transformed into an equivalent set of 2-sat/Hornsat/affine clauses (using auxiliary variables) or just that this would be very unlikely in that it would imply P = NP? I ask because I know that there are some types of problems involving 3-literal-clauses which can be transformed into equivalent 2-sat/Hornsat clauses. I'm thinking specifically of 2-or-3 SAT which can be solved by 2-sat/anti-Hornsat clauses or 1-or-3 SAT which can be solved using affine clauses.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top