Prev: Note on MacLaren and Marsaglia's randomizing by shuffling
Next: semi-Hamiltonian paths in planar triangulations
From: Sadeq on 12 Jun 2010 05:57
Hi there!

The polynomial-time hierarchy (PH) is simply defined in a recursive
manner.

For example, for all k>=0, the \Sigma_{k+1} complexity class is
defined as NP^\Sigma_k.

My question is, whether on can write \Sigma_{k+1} as \Sigma_k^NP ?

This is somehow counterintuitive, but I saw a variation of it in the
following paper:

Vikraman Arvinda, Johannes Köblerb, Uwe Schöningb, Rainer Schuler,
"If
NP has polynomial-size circuits, then MA = AM" Theoretical Computer
Science, 1995.
From: tchow on 12 Jun 2010 19:33
In article <9effea81-20b9-41a7-8f76-ca29863bc530(a)q12g2000yqj.googlegroups.com>,
Sadeq <msdousti(a)gmail.com> wrote:
>For example, for all k>=0, the \Sigma_{k+1} complexity class is
>defined as NP^\Sigma_k.
>
>My question is, whether on can write \Sigma_{k+1} as \Sigma_k^NP ?

Maybe I don't quite understand your question, but \Sigma_k will in
general contain NP so what benefit does it get from an NP oracle?
--
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: Sadeq on 13 Jun 2010 07:31
> >My question is, whether on can write \Sigma_{k+1} as \Sigma_k^NP ?
> Maybe I don't quite understand your question, but \Sigma_k will in
> general contain NP so what benefit does it get from an NP oracle?

I don't think things are that simple. For example, NP is trivially
contained in NP, but NP^NP is a legitimate complexity class, also
known as \Sigma_2. Most scientists believe that \Sigma_2 does not
collapse to NP.
From: tchow on 13 Jun 2010 13:09
In article <33282a15-04ac-43a2-8905-3fe75c8cf1e6(a)z31g2000vbk.googlegroups.com>,
Sadeq <msdousti(a)gmail.com> wrote:
>> >My question is, whether on can write \Sigma_{k+1} as \Sigma_k^NP ?
>> Maybe I don't quite understand your question, but \Sigma_k will in
>> general contain NP so what benefit does it get from an NP oracle?
>
>I don't think things are that simple. For example, NP is trivially
>contained in NP, but NP^NP is a legitimate complexity class, also
>known as \Sigma_2. Most scientists believe that \Sigma_2 does not
>collapse to NP.

You're right about that...not the first time I've fallen into that trap!
Let me think about it again.
--
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: tchow on 13 Jun 2010 17:01
In article <9effea81-20b9-41a7-8f76-ca29863bc530(a)q12g2000yqj.googlegroups.com>,
Sadeq <msdousti(a)gmail.com> wrote:
>My question is, whether on can write \Sigma_{k+1} as \Sigma_k^NP ?

O.K., now I have a question for you. What exactly do you mean by
\Sigma_k^NP? The notation is somewhat misleading; oracles can't be
directly attached to languages. They have to be attached to models
of machines. Thus NP^\Sigma_k makes sense because it means you're
looking at non-deterministic machines with access to a \Sigma_k oracle.
But a priori, \Sigma_k is just a language, not a machine model. Until
you specify a machine model, it doesn't make sense to give it access
to an oracle.
--
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
 |  Next  |  Last
Pages: 1 2 3
Prev: Note on MacLaren and Marsaglia's randomizing by shuffling
Next: semi-Hamiltonian paths in planar triangulations