1

As far as I understand all languages in NP are decidable. But not all decidable Languages are in NP, because NP only contains decision problems. Are there also decision problems that are decidable but not in NP?

What is the relationship between NP and context-free/regular languages? Are there context-free languages in NP? Are there regular languages in NP?

Are there languages in NP that are not context-free? Are there languages in NP that are not regular?

2 Answers2

5

Basic Facts:

  • CYK-algorithm parses inputs of length $n$ for any CFG in Chomsky normal form in time in $\mathcal{O}(n^3)$
  • Every CFL is generated by a CFG in Chomsky normal form
  • Every regular language is (also) context-free.

That answers immediately all those questions:

What is the relationship between NP and context-free/regular languages? Are there context-free languages in NP? Are there regular languages in NP?

$\{a^nb^nc^n \mid n \geq 0\}$ is not context-free (by pumping lemma). It can obviously be decided by a (D)TM in quadratic time. That answers:

Are there languages in NP that are not context-free? Are there languages in NP that are not regular?

And as for

Are there also decision problems that are decidable but not in NP?

Yes, see Problems that cannot be verified in polynomial time

Community
  • 1
Raphael
  • 4,565
  • 28
  • 48
  • 3
    Raphael, since you also expressed doubts about the scope, it might be best to wait on answering, since answering defeats the purpose of limiting questions to research-level. – Suresh Venkat Jan 27 '11 at 17:34
  • Sorry, you guys are usually faster. Figured it was not to be closed (can't see the votes, doh). Also, I wanted to give a more concise und (hopefully) precise answer than Kevin's. – Raphael Jan 27 '11 at 18:39
1

There are notions of equivalence between languages, algorithms, and recursive functions; however it is important not to mix the terminology associated with each of these.

For instance, some classes of languages are: regular, context-free, context sensitive, unrestricted. Language classes are not themselves in P or NP. Language classes are defined by imposing constraints on generative grammar rules. A language is in a given class if there exists at least one grammar that generates it and satisfies the constraints of the class.

As you noted, there are classes of problems. Some problems are the recognition of languages, and this is how we relate problem classes to language classes. A problem is decidable if there exists at least one Turing machine that halts (concludes true or false) on every possible input. A problem is in P is there exists at least one deterministic Turing machine that decides any possible input in a number of steps that is bounded by a polynomial function of the input length. In contrast, NP is essentially the same except that it allows the Turing machine to be non-deterministic -- a powerful concept.

Now you can see the difference between language and algorithm families. Take the family of context-free languages. For any such a language, there is an algorithm which recognises sentences in that language, and does so deterministically in polynomial time. That algorithm is in P.

If we instead consider a context sensitive language, then any algorithm that recognises its sentences will (for some input) require non-deterministic choice in order to prevent going beyond polynomial time (assuming P != NP). Of course, if we simulate non-deterministic choice with a strategy like backtracking, we typically exceed polynomial time.

Now I will try to reinterpret your questions.

  • Are there languages which are decidable, but not always in non-deterministic polynomial time (ie. for which an algorithm exists, but no algorithm is in NP)?

I must confess: I don't know. Has anyone given this thought?

  • What is the relationship between NP and context-free/regular languages?

Answered in discussion.

  • Are there context-free languages which are not decidable in P, but are decidable in NP?

There are algorithms in P which solve any context-free language decision problem. For example, the Earley parser.

  • Are there regular languages decidable in NP?

All regular languages are decidable in P. (Consequently, they are also decidable in NP.)

  • Are there languages in NP that are not context-free?
  • Are there languages in NP that are not regular?

I think the asker means to ask if there are such languages, not decidable in P. This is a loaded question because is deals with P=NP as well as the context-free issue. As stated, all context-free languages are decidable in P, so lets remove that part of the question. I think what is then being asked is this: are there languages decidable in NP, but not in P? This asks if P != NP -- and the truth is we just don't know. I am fairly sure that most CS people believe P != NP, which implies that such languages do exist. However, no proof has been found as yet.

I have not addressed the third arm, recursively enumerable, because the Skiy didn't mention it.

(If anyone spots any mistakes here, please offer corrections. This was my first response here.)

Kevin A. Naudé
  • 119
  • 2
  • Wow, long! You seem to assume $CFL = P$ (modulo abuse of notation). But clearly ${ww \mid w \in {a,b}}$ is not in CFL, but in P. P?=NP has nothing to do with the questions stated by the OP. – Raphael Jan 27 '11 at 17:15
  • @Raphael: Thanks for the comment. I was not assuming CFL=P, rather I used CFL as an example as the asker was familiar with context-free. The original questions said nothing about P=NP because the asker did not realise the connection. You are correct about {ww|w in {a,b}+}, but that answers a question that wasn't asked. It answers the question: are there non-context-free languages decidable in P? Your example shows yes. – Kevin A. Naudé Jan 27 '11 at 17:45