5
votes
How is $\overline{SAT}$ not obviously in NP?
The problem is that you have to convince that NO assignment can satisfy the formula, and that cannot be done easily non-deterministically.
For the problem $\mathsf{SAT}$, a certificate can be a ...
- 18.4k
2
votes
How is $\overline{SAT}$ not obviously in NP?
The algorithm you describe runs in $P^{NP}$, not in $NP$. (And yes, $\overline{SAT}\in P^{NP}$)
A nondeterministic Turing-machine $M$ accepts an input $x$ iff there is a sequence of nondeterministic ...
Only top scored, non community-wiki answers of a minimum length are eligible