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 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 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 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