How do you determine if a language falls into NP?
-
29-10-2019 - |
Pergunta
for example, I know that the language
isnt context free by the pumping lemma for CFLs, but how would i prove that it falls into NP and not exp. time, decidable languages, or turing recognizable?
EDIT: Did some digging, and one oversight i made is that problems in NP are those that a verifiable in polynomial time BY a Nondeterministic Turing Machine. How would I know: a: There is a verifier that exists for this language in polynomial time and b: a NDTM can recognize it
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow