Prev: Note on MacLaren and Marsaglia's randomizing by shuffling
Next: semiHamiltonian paths in planar triangulations
From: Sadeq on 12 Jun 2010 05:57 Hi there! The polynomialtime 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 polynomialsize circuits, then MA = AM" Theoretical Computer Science, 1995.
From: tchow on 12 Jun 2010 19:33 In article <9effea8120b941a78f76ca29863bc530(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 tchowatalumdotmitdotedu The range of our projectileseven ... the artilleryhowever 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 <33282a1504ac43a289053fe75c8cf1e6(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 tchowatalumdotmitdotedu The range of our projectileseven ... the artilleryhowever 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 <9effea8120b941a78f76ca29863bc530(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 nondeterministic 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 tchowatalumdotmitdotedu The range of our projectileseven ... the artilleryhowever 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: semiHamiltonian paths in planar triangulations 