Skip to main content

Questions tagged [schaefers-dichotomy]

Any question that asks whether SAT with the following constraints is NP-complete or not

Filter by
Sorted by
Tagged with
0 votes
1 answer
86 views

Complexity of this variant of 3-SAT?

This post introduces a new variant of 3-SAT called EQUAL-3-SAT, where the number of 3-Literal clause is equal to the number of variable. Consider the 3-SAT problem where the formula is in conjunctive ...
Anuj's user avatar
  • 43
2 votes
1 answer
287 views

Is checking whether a a set of 3-literal clause is satisfiable such that every literal in each clause is either all true or all false NP-complete?

I want to know if checking whether a a set of 3-literal clause is satisfiable such that every literal in each clause is either all true or all false NP-complete? By 3-literal clause, I mean it can ...
Anuj's user avatar
  • 43