Why is the complement of SAT not in NP?

Question

I know that you cannot give a verification certificate. But, I was just thinking, why can't we give the input to an NDTM deciding SAT, and then reverse the answer? Where is the flaw?

Answer 1

It's actually not known whether the complement of SAT is in NP. If P = NP, then since all P languages are closed under complementation, then the complement of SAT must be in NP (since it's in P). Otherwise, if the complement of SAT is not in NP, then P ≠ NP by using similar logic.

It's suspected that the complement of SAT is not in NP because the complement of SAT consists (ignoring garbage malformed strings) of propositional formulas that are unsatisfiable. It's unclear what information you could nondeterministically guess that would help you determine whether a formula never evaluates to true, whereas in the case of SAT it's easy to nondeterministically guess a satisfying assignment to check whether a formula is indeed satisfiable.

As for the error in your reasoning - an NTM accepts iff there is some accepting branch of the computation. If you flip all "accepts" to "rejects," then you don't flip the overall result of the computation. To flip the computation result, you'd have to have the complemented NTM accept iff every branch accepts, versus if at least one branch accepts.

Hope this helps!