New answers tagged

0

Polynomial reduction and certificates have very little to do with each other. Basically, we defined the set P of all easy problems that can be solved by a computer in polynomial time. Then obviously problems not in P are hard. We then defined the set NP of all problems which can be solved in polynomial time by a non-deterministic computer, in other ...


2

As confirmed independently in another answer, 2P2N-3SAT is already NP-complete. Another name for the fragment you are interested in is (3, B$k$)-SAT where "B" stands for Balanced and indicates that there are the same number of positive and negative occurences of the variables, $k$ is the number of positive and the number of negative occurences, and the 3 ...


Top 50 recent answers are included