Prev: Second CALL FOR PAPERS: WfPM'08, September 2008, Timisoara, ROMANIA
Next: Word problems for grammars
From: sanchopancho80 on 3 Jul 2008 10:43
Hello,
I have a few questions on complexity theory which are perhaps easy to
answer for an expert or perhaps at least for a beginner in the field.

1. Is the problem CLIQUE(n) that decides weather an input graph has
got an n-clique or not in NP? I suppose it is, because I know that
CLIQUE (that gives the maximal clique of an input graph) is in NP.

2. Is it true that the class of languages generated by all context
sensitive grammars which is called the "type 1 languages" is PSPACE
complete (which means that the word problem for type 1 languages is
PSPACE complete)?

3. Have you got a common example for a P-complete language? Perhaps
the type 2 word problem (languages generated by context free grammars)
which is in P by the CYK algorithm?

4. Is it true that the problem of determining the chromatic number for
an input graph is in NP? I know that "3-colorability" is NP complete.

5. If you want to test weather a given decimal number n is a prime or
not you can do this in \sqrt(n) steps which is bounded by a
polynomial. This does not mean that PRIMES is in P because the input
is in decimal form. What is the complexity of testing the \sqrt(n)
factors? Perhaps 2^\sqrt(n)?

Thanks,
S.
From: tchow on 3 Jul 2008 11:30
In article <ee615942-4503-43bf-9019-d4ded0bcb6a2(a)f36g2000hsa.googlegroups.com>,
<sanchopancho80(a)web.de> wrote:
>1. Is the problem CLIQUE(n) that decides weather an input graph has
>got an n-clique or not in NP? I suppose it is, because I know that
>CLIQUE (that gives the maximal clique of an input graph) is in NP.

If n is fixed, then the problem of deciding whether CLIQUE has an n-clique
is polytime-solvable. Simply check all n-tuples of vertices for a clique.

>2. Is it true that the class of languages generated by all context
>sensitive grammars which is called the "type 1 languages" is PSPACE
>complete (which means that the word problem for type 1 languages is
>PSPACE complete)?

It's *languages* that are (or are not) PSPACE-complete, not *classes* of
languages. Perhaps you intend to ask if the problem of determining whether
a given string is generated by a given CSG is PSPACE-complete; the answer
is yes. However, this is not literally what you asked, so maybe I'm
misinterpreting your question.

>3. Have you got a common example for a P-complete language? Perhaps
>the type 2 word problem (languages generated by context free grammars)
>which is in P by the CYK algorithm?

http://en.wikipedia.org/wiki/P-complete

>4. Is it true that the problem of determining the chromatic number for
>an input graph is in NP? I know that "3-colorability" is NP complete.

NP is, strictly speaking, a class of *decision* problems. Here you are
asking for the computer to return a number, not just a yes/no answer.

It is NP-complete to ask, given a graph G and a number k, is the chromatic
number of G <= k?

>5. If you want to test weather a given decimal number n is a prime or
>not you can do this in \sqrt(n) steps which is bounded by a
>polynomial. This does not mean that PRIMES is in P because the input
>is in decimal form. What is the complexity of testing the \sqrt(n)
>factors? Perhaps 2^\sqrt(n)?

PRIMES is known to be in P by work of Agrawal, Kayal, and Saxena.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: sanchopancho80 on 3 Jul 2008 15:26
Hello and thank you for your answer. Nevertheless I have some
questions yet.

On 3 Jul., 17:30, tc...(a)lsa.umich.edu wrote:
> In article <ee615942-4503-43bf-9019-d4ded0bcb...(a)f36g2000hsa.googlegroups..com>,
>
>  <sanchopanch...(a)web.de> wrote:
> >1. Is the problem CLIQUE(n) that decides weather an input graph has
> >got an n-clique or not in NP? I suppose it is, because I know that
> >CLIQUE  (that gives the maximal clique of an input graph) is in NP.
>
> If n is fixed, then the problem of deciding whether CLIQUE has an n-clique
> is polytime-solvable.  Simply check all n-tuples of vertices for a clique.

Ok, let's get more precise: Consider an alphabet S and choose a simple
coding for a graph over this alphabet, i.e. 'encode' the incidence
matrix of a graph. There is a context free grammar which produces all
such representations of graphs, hence the word problem for this 'graph-
language' G is in P which is you can decide in polynomial time weather
an arbitrary string x of S* is in G or not. Moreover there is an
encoding for all natural numbers over this alphabet, e.g. a unary
representation of the number and this is generated by a simple context
free grammar, too. So you can form the language G' which consists of
all encoded pairs (G,k) where G is a graph and k is a natural number.
You can decide in polynomial time weather an arbitrary string of S' is
in G' (which is that this string is an encoding of a pair (G,k)) or
not. Lets write <G,k> for the encoding of such a pair.

For me, CLIQUE(n) denotes the word problem for the language C_n={<G,k>|
k=n and G is a finite graph and G has a k-clique} in S*. By the above
discussion you can ignore inputs which are not of the form <G,k>
because deciding weather an arbitrary string x of S* is of the form
<G,k> can be done in polynomial time. Finally CLIQUE is the word
problem for the language C="union of all C_n"={<G,k>|G is a finite
graph and G has a k-clique} for me. What is your definition of CLIQUE
and CLIQUE(n) in this context? Do you agree with mine?

I can show that CLIQUE is NP-complete. In addition I think that if
CLIQUE(n) is in P (as you have stated as far as I have understood it)
then CLIQUE is in P too which seems to be wrong. The argument is the
following: Suppose CLIQUE(n) is in P for every natural number n and
you get an encoded <G,k> as an input for which you have to show
weather it is in C or not (by the above discussion you have not to
look at any string x of S*). Then simply run CLIQUE(k) which can be
done in deterministic polynomial time. If it says 'yes' then <G,k> is
a member of C and in the other case it is not. Where is my mistake?
Even if you define a language C'={<G,k>|G is a finite graph and G has
a k-clique and no k+1-clique} (maybe this is meant by CLIQUE?) and
consider the word problem (which 'determines' the maximal cardinality
of a clique of an imput graph) it should be in P if CLIQUE(n) is in P:
Just test CLIQUE(i) for all i=1...i=|vertices of G| and get an answer
in |vertices of G|*polynomial=polynomial time.

> >2. Is it true that the class of languages generated by all context
> >sensitive grammars which is called the "type 1 languages" is PSPACE
> >complete (which means that the word problem for type 1 languages is
> >PSPACE complete)?
>
> It's *languages* that are (or are not) PSPACE-complete, not *classes* of
> languages.  Perhaps you intend to ask if the problem of determining whether
> a given string is generated by a given CSG is PSPACE-complete; the answer
> is yes.  However, this is not literally what you asked, so maybe I'm
> misinterpreting your question.

I am sorry. This is exactly what I mean. By a class to be PSPACE-
complete I mean that every language of it is PSPACE and there are
PSPACE-complete ones among them but nevermind...

> >4. Is it true that the problem of determining the chromatic number for
> >an input graph is in NP? I know that "3-colorability" is NP complete.
>
> NP is, strictly speaking, a class of *decision* problems.  Here you are
> asking for the computer to return a number, not just a yes/no answer.
> It is NP-complete to ask, given a graph G and a number k, is the chromatic
> number of G <= k?

Ok, thanks.

> >5. If you want to test weather a given decimal number n is a prime or
> >not you can do this in \sqrt(n) steps which is bounded by a
> >polynomial. This does not mean that PRIMES is in P because the input
> >is in decimal form. What is the complexity of testing the \sqrt(n)
> >factors? Perhaps 2^\sqrt(n)?
>
> PRIMES is known to be in P by work of Agrawal, Kayal, and Saxena.

Thanks but I know that this remarkable result does exist. Anyway I
wonder what my problem with the naive approach from above could be.

Thanks,
S.


From: Bryan Olson on 4 Jul 2008 06:25
sanchopancho80(a)web.de wrote:
> tc...(a)lsa.umich.edu wrote:
>> <sanchopanch...(a)web.de> wrote:
>>> 1. Is the problem CLIQUE(n) that decides weather an input graph has
>>> got an n-clique or not in NP? I suppose it is, because I know that
>>> CLIQUE (that gives the maximal clique of an input graph) is in NP.

>> If n is fixed, then the problem of deciding whether CLIQUE has an n-clique
>> is polytime-solvable. Simply check all n-tuples of vertices for a clique.
>
> Ok, let's get more precise: [...]

> I can show that CLIQUE is NP-complete. In addition I think that if
> CLIQUE(n) is in P (as you have stated as far as I have understood it)
> then CLIQUE is in P too which seems to be wrong. The argument is the
> following: Suppose CLIQUE(n) is in P for every natural number n and
> you get an encoded <G,k> as an input for which you have to show
> weather it is in C or not (by the above discussion you have not to
> look at any string x of S*). Then simply run CLIQUE(k) which can be
> done in deterministic polynomial time. If it says 'yes' then <G,k> is
> a member of C and in the other case it is not. Where is my mistake?

For each language in CLIQUE(n), there is polynomial function
of the input length that bounds the time to decide the
language. The polynomials may be different for different n.
An algorithm is not poly-time if you have to keep upping the
polynomial as the length of the input increases.

Perhaps an example would help. Suppose I have an algorithm
that decides any language in CLIQUE(n) in time 2**n * |G|**3.
For all n, the algorithm solves CLIQUE(n) in poly-time, but
it takes exponential time to solve general CLIQUE.


--
--Bryan

From: Andrea Moro on 4 Jul 2008 06:53
sanchopancho80(a)web.de wrote:
> 5. If you want to test weather a given decimal number n is a prime or
> not you can do this in \sqrt(n) steps which is bounded by a
> polynomial. This does not mean that PRIMES is in P because the input
> is in decimal form. What is the complexity of testing the \sqrt(n)
> factors? Perhaps 2^\sqrt(n)?

time complexity needs to be considered in the length of the input, in that
case the length of the input is logn so your algorithm takes
O(sqrt(2^logn)) that is exponential in the length of the input.
 |  Next  |  Last
Pages: 1 2 3
Prev: Second CALL FOR PAPERS: WfPM'08, September 2008, Timisoara, ROMANIA
Next: Word problems for grammars