Prev: Complexity theory
Next: Question on Sipser example proof
From: sanchopancho80 on 3 Jul 2008 17:01
Hello,

i am sorry for asking another pack of questions but sadly I don't know
what I should do otherwise to get answers to problems I am stuck on.

1. You can speak of problems (which are always word problems to me) in
P and NP without giving any alphabet because it does not matter, i.e.
if you formulate a problem with 100 symbols then you can encode each
of them and get a 2-symbol formulation. But what about complexity
classes like L=(log space problems) or NL? Does the alphabet matter in
this case or is the 'encoding procedure' from above computable in
logarithmic space?

2. I wonder if the word problem for type 3 languages (which are given
by regular expressions, automata, etc.) is in L. Is this true? The
type 2 word problem is in P because the CYK algorithm is a polynomial
time one, right? What about the type 1 word problem (context sensitive
languages), is it perhaps in PSPACE?

3. Well, after 10.000 posts on "NP=P?" in this newsgroup I'll start
another one: Is it theoretically possible to find a proof that the
"proof of NP=P or NP!=P" is in NP itself? (this should be considered
as the decision problem weather the set of proofs of the statement is
empty) If this is the case, does it mean, that it is impossible to
find a proof or disproof for "NP=P"? If one can show that the "proof
of NP=P or NP!=P" is in P, does this mean that one is able to
construct a proof at once?

Thanks,
S.
From: sanchopancho80 on 4 Jul 2008 08:22
Hello,

I have seen that some of my questions are stated in a bad way, so I
like to state them in a better one now.

> 1. You can speak of problems (which are always word problems to me) in
> P and NP without giving any alphabet because it does not matter, i.e.
> if you formulate a problem with 100 symbols then you can encode each
> of them and get a 2-symbol formulation. But what about complexity
> classes like L=(log space problems) or NL? Does the alphabet matter in
> this case or is the 'encoding procedure' from above computable in
> logarithmic space?

This question remains as it was.

> 2. I wonder if the word problem for type 3 languages (which are given
> by regular expressions, automata, etc.) is in L. Is this true? The
> type 2 word problem is in P because the CYK algorithm is a polynomial
> time one, right? What about the type 1 word problem (context sensitive
> languages), is it perhaps in PSPACE?

Well. what does 'word problem for type 3 languages' mean? This was
badly formulated, so please let me do it again:
If you take a finite automaton A which generates a language L_A over
some alphabet S, you can speak of the complexity of the word problem
'is an arbitrary string of S' in L_A or not' which is clearly
decidable. Is it decidable in log-space?
Now consider the same situation for a context-free-grammar: Take a
context free grammar G which generates a language L_G over some
alphabet S. The word problem for L_G is decidable and decidable in
polynomial time by the CYK algorithm. What happens if you take a
context sensitive grammar instead of a context free one? Is the
resulting word problem in PSPACE?

> 3. Well, after 10.000 posts on "NP=P?" in this newsgroup I'll start
> another one: Is it theoretically possible to find a proof that the
> "proof of NP=P or NP!=P" is in NP itself? (this should be considered
> as the decision problem weather the set of proofs of the statement is
> empty) If this is the case, does it mean, that it is impossible to
> find a proof or disproof for "NP=P"? If one can show that the "proof
> of NP=P or NP!=P" is in P, does this mean that one is able to
> construct a proof at once?

This makes completely no sense and I am sorry for such a bad question.
Is there any meaningful formulation of the complexity of the problem
of deciding if 'finding a proof weather NP=P or NP!=P' holds?

Thanks,
S.
 | 
Pages: 1
Prev: Complexity theory
Next: Question on Sipser example proof