show that NP is a subset of decidable languages More specifically the problem says: &quot;Let us call the set of decidable languages D. Show that NP ⊆ D&quot;
My problem is that I always assumed that NP is decidable, but to prove it, I never thought it
Somebody have any idea about how do it? or start resolving it?
I think I can prove it saying something like the NP problems effectively end in a polynomial time (although not deterministic) so there must be a MT-ND that accepts it and always ends, I suposse
Every language that is in NP is by definition decidable. Becase if a language L is in NP, than there is a nondeterministic Turing Machine that decides it in polynomial time, and thus L is decidable.