Science Talk

Guest · Posted: Thu Jul 10, 2008 8:50 am Post subject: Problem with complexity problem

Hello,

take a grammar G with alphabet {0,1} such that (the word problem for)
the language
L_G={w in (0+1)*|w\in L(G)}
is very complex, say in PSPACE or some higher complexity class.

Now consider an "easy" problem EASY like: "Is an element of L_G in
L_G?". Well, this seems to be fairly easy because the answer is "yes"
in any case. Hence the problem should be of small complexity.

But if one models such a decision problem one has to construct a
language L with alphabet A such that the word problem for L reflects
exactly the decision problem which one is interested in. For example
the problem CLIQUE has been modeled by the word problem for the
language L_CLIQUE={<G,k> in (0+1)* | G finite graph, k natural number
and G has a k-clique}.

Now my problem arises: In the CLIQUE case one can think of an "input"
of the turing machine T which should decide the word problem for
L_CLIQUE already as a pair <G,k> in the wanted form and one has not to
consider an arbitrary string x of (0+1)*. This is possible because the
language L'={<G,k> in (0+1)* | G finite graph, k natural number} can
be produced by an easy context-free grammar and therefore the word
problem for L' is of a low complexity like P. So if one considers the
word problem for the language L_CLIQUE one can decide in P if an
arbitrary string x of (0+1)* is of the form <G,k> and if it is not the
turing machine T can stop without accepting immediately. Therefore the
complexity of L_CLIQUE is polynomial+"complexity of the real problem
CLIQUE".

But what happens in the above case where the word problem for L_G is
rather difficult? Even if the "real problem" is very easy the
complexity of L_G would be exponential+"complexity of the real problem
EASY". Hence the problem EASY is a very complex one, right?

* An example for such a language L(G) is perhaps the following one:
In a previous post it has been shown to me that the language L={e,
1,11,1111,11111111,...} is not context-free but context-sensitive and
the word problem for arbitrary context-sensitive languages is more
complex than PSPACE so this language L has a great chance to be such
complex.

* For a language L it is defined to be in a complexity class, e.g. P
or PSPACE, iff the word problem of that language is in that complexity
class.

Thanks,
Sancho