Pergunta

Is the problem of deciding whether a SAT instance, where at most two clauses are false (that is, any given variable assignment will either lead to all clauses being true, all but one, or all but two), is satisfiable solvable in polynomial time?

This is a follow-up from my previous question. The problem presented in that question (at most one false clause) was solvable in polynomial time, because we could take advantage of the fact that the set of truth assignments that make a clause false is disjoint to that of any other clause. With two or more clauses, the sets that make a clause false can overlap with each other. Does this mean that problems with at most two (or more) false clauses (when I say "or more," I do not mean that the number can change with the problem size. A problem with five clauses where at most five are false is a trivial version of regular SAT, but what about a problem of a few million clauses where are most five can be false?) are NP-complete, or are all versions of SAT where you limit the number of false clauses solvable in polynomial time?

Nenhuma solução correta

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