CODEWITHSUNDEEP
computer-scienceturing-machinesnp
jfisk
jfisk

Reputation: 6205

How do you determine if a language falls into NP?

for example, I know that the language enter image description here

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

Upvotes: 1

Views: 3361

Answers (1)

Prateek
Prateek

Reputation: 2397

but how would i prove that it falls into NP and not exp. time, decidable languages, or turing recognizable?

You cannot, because that cannot happen. Every language in NP is in EXPTIME, is decidable, and is Turing recognizable. L is in NP if and only if there is a polynomial p and a PTIME language L' such that

x in L if and only if there exists y of length p(|x|) such that (x,y) is in L'

To show that NP is a subset of EXPTIME, observe that one can just do a brute-force search for all possible y. And every EXPTIME langauge is obviously decidable and recognizable.

Now, as for your question about showing a language L belongs to NP : Try to come up with a way by which for each x in L, you can write down a "proof" or "certificate" that it belongs to L. Such a certificate should not exist for x not in L, and that this certificate is correct should be efficiently verifiable (in polynomial time). The length of the certificate should itself be at most polynomial in the length of x.

Exactly how one does this depends on the particular language L, of course. Many NP problems are phrased as search (existence) problems : does this graph have a Hamiltonian cycle, does this boolean formula have a satisfying assignment, and so on. In this case, the choice for the certificate is usually clear, one can take the certificate to be the thing being searched for (the Hamiltonian path or satisfying assignment itself). One needs to check that given a graph and an alleged Hamiltonian path, one can check if it is actually a Hamiltonian path in polynomial time, or given a formula and an alleged satisfying assignment, one can check if it is actually a satisfying assignment in polynomial time. This is usually easy to show.

Note that P is a subset of NP (just take anything for the certificate, the certificate-checker can solve the original problem itself in polynomial time). The language you asked for, {a^n b^n c^n | n >= 0} is quite easily in P (and hence in NP).

Upvotes: 2

Related Questions