I understand why NP=coNP if SAT is in coNP (How do I prove that SAT in coNP implies NP=coNP?).
But I’m missing why the following machine doesn’t turing recognize the complementary of SAT:
Given a turing machine M that recognizes SAT, the following turing machine recognizes coSAT:
- Run M on the input word w.
- If M accepts – reject.
- If M rejects – accept.
Because coSAT is the language of all unsatisfiable formulas, a formula is unsatisfiable if it doesn’t have a satisfiable interpretation, which is exactly the opposite of what M outputs.
What am I missing in here?