6 votes
Accepted

Nondeterministic Turing Machines as deciders, versus NP and co-NP

As requested, I write up my comment as an answer, hoping that I correctly understood the misunderstanding :-) Li-yao Xia's answer already clarifies that, in the context of complexity, there are only ...
Damiano Mazza's user avatar
3 votes

Nondeterministic Turing Machines as deciders, versus NP and co-NP

The comments have covered a lot of ground already. I just wanted to clarify a couple of minor points about the decider/recognizer and deterministic/nondeterministic distinctions. In the context of P ...
Li-yao Xia's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible