I am aware that satisfiability is NP complete and unsatisfiability is co-NP complete. But somehow I feel that labeling satisfiability as NP-complete and unsatisfiability as co-NP complete is papering over the fact that unsatisfiability (or equivalently validity) is inherently a harder problem than satisfiability. Suppose I have a NDTM. Then given a potential model I can surely check it in polynomial time. However to check unsatisfiability I would need to check all possible assignments, surely this makes the problem EXPTIME?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
However to check unsatisfiability I would need to check all possible assignments, surely this makes the problem EXPTIME?
Well, $EXPTIME$ but not necessarily $EXPTIME$-complete.
Congratulations, you've found the (possible) difference between $NP$ and $Co-NP$.
The first thing to realize is that there's a duality here. Satisfiability requires only a single example to prove a YES, but (as far as we know) needs to search a possibly exponential space for a NO. Unsat is the exact dual of this: you need to search a possibly exponential set to prove a YES, but a single counter-example will prove a NO. So neither is a harder problem, it's just that one is easy for YES, and the other is easy for NO.
The second thing to realize is that every NP-complete problem has a dual like this, and that's exactly why we study $Co-NP$ complete problems. For Hamiltonian Path, one path proves it, and a full search is needed to disprove. The converse is true to for NOHAMPATH, it's complement problem. Every NP-problem has a dual by switching the "yes" and "no" cases.
Nobody knows if $NP = EXPTIME$, though it's pretty unlikely. But it seems like just having to do an exponential search isn't enough to characterize all exponential algorithms.
answered Sep 1, 2017 at 20:35
-
$\begingroup$ I'm not sure I completely follow your explanation. What does it mean to say boolean satisfiability is easy for YES and hard for NO. For boolean satisfiability to be NP-complete wouldn't that require that a NDTM be able to answer both YES or NO (as appropriate) in a polynomial number of steps (in the input size)? $\endgroup$ Commented Sep 5, 2017 at 6:26
-
$\begingroup$ @S.N. Right, but there's an inherent imbalance between YES and NO for how you convert an NTM to DTM. YES requires that there exists a successful execution, whereas NO requires that all halting executions fail. So to prove that an NTM says YES on a given input, you need only provide one trace, but you need to elaborate all traces to prove that it answers NO. In an actual DTM solving SAT you might need to do an exponential number of steps to find an answer if it's YES, but you might get lucky and find one sooner. There's no known way to "get lucky" with NO. $\endgroup$ Commented Sep 5, 2017 at 18:01
$\begingroup$
$\endgroup$
No, it just means that there's no obvious algorithm for a nondeterministic Turing machine to check unsatisfiability in polynomial time, which is part of the reason why we don't know if NP and co-NP are the same thing.
For deterministic machines, unsatisfiability can't be harder than satisfiability since, if you could solve either one, you could solve the other by negating the answer. Negating the answer is non-trivial for nondeterministic machines.
answered Sep 1, 2017 at 20:31