I think the best way to explain my question would be to have sextuple (regular, context-free, Turing-recognisable, decidable, P, NP).were you fill out 1 for promblem which lies into that section, would an np problem such as chess be only 1 for NP or would also fall in decidable?

Some other examples: The regular problem would be (1,1,1,1,1,1) as regular is a subset of CF,TR, Decidable which runs in P time and NP is a subset of NP.

Another example, a context-free language would be (0,1,1,1,1,1).

and I assume chess would be (0,0,1,1,0,1)

So my question is would my assumption on NP problems be correct as some decider has to recognize them?

  • $\begingroup$ Chess is not an NP problem, in the sense it is not within the complexity class NP. It's an NP-hard problem. $\endgroup$
    – rus9384
    May 17, 2023 at 18:28

1 Answer 1


Yes, this is correct, due to the computational equivalence of nondeterministic turing machines to deterministic ones. You can try all possible certificates in exponential time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.