Prev: Note on MacLaren and Marsaglia's randomizing by shuffling
Next: semi-Hamiltonian paths in planar triangulations
From: Sadeq on 14 Jun 2010 05:51
On Jun 14, 1:01 am, tc...(a)lsa.umich.edu wrote:
> O.K., now I have a question for you.  What exactly do you mean by
> \Sigma_k^NP?

To simplify, let k=2.
Let M be a Turing machine which can decide \Sigma_2 = NP^NP. That is,
for every L \in NP^NP and every x, M(x) equals 1 if and only if x \in
L, and 0 otherwise. Such a machine is a legitimate Turing machine.

Now, lets give this machine an NP oracle. What languages can M^NP
decide?

My exact question is, whether the "set of languages decidable by M^NP"
equals NP^(NP^NP)?
From: tchow on 14 Jun 2010 16:54
In article <823ae1ae-12a6-4c89-b551-66bfa163281e(a)y4g2000yqy.googlegroups.com>,
Sadeq <msdousti(a)gmail.com> wrote:
>On Jun 14, 1:01�am, tc...(a)lsa.umich.edu wrote:
>> O.K., now I have a question for you. �What exactly do you mean by
>> \Sigma_k^NP?
>
>To simplify, let k=2.
>Let M be a Turing machine which can decide \Sigma_2 = NP^NP. That is,
>for every L \in NP^NP and every x, M(x) equals 1 if and only if x \in
>L, and 0 otherwise. Such a machine is a legitimate Turing machine.
>
>Now, lets give this machine an NP oracle. What languages can M^NP
>decide?
>
>My exact question is, whether the "set of languages decidable by M^NP"
>equals NP^(NP^NP)?

I'd have to think about this a bit more, but I'm pretty sure that the
answer is no, and that this class of languages is not very well-behaved,
because you've defined it "semantically." That is, you're singling out
a class of machines based on an undecidable property (namely, what
languages they accept). In particular, I suspect that you won't be able
to come up with complete problems for your classes.

If I figure out anything more definitive I'll post here later.
--
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 14 Jun 2010 21:56
On Jun 15, 12:54 am, tc...(a)lsa.umich.edu wrote:
> I'd have to think about this a bit more, but I'm pretty sure that the
> answer is no, and that this class of languages is not very well-behaved,
> because you've defined it "semantically."  That is, you're singling out
> a class of machines based on an undecidable property (namely, what
> languages they accept).  In particular, I suspect that you won't be able
> to come up with complete problems for your classes.
>
> If I figure out anything more definitive I'll post here later.

Thanks. In fact, I'm not defining it my way. As I posted earlier, I
found 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.

There, they used the result of Sipser: BPP \subseteq NP^NP.

Then, they relativized this using an NP oracle:

BPP^NP \subseteq (NP^NP)^NP.

Finally, they claimed the right-hand side is \Sigma_3.

This is while we know that \Sigma_3 = NP^(NP^NP).

So, I asked whether (NP^NP)^NP = NP^(NP^NP)?

If not, their claim is wrong.
From: tchow on 15 Jun 2010 01:08
In article <e5686ad0-92d6-4666-8c8f-e14f905693ec(a)c33g2000yqm.googlegroups.com>,
Sadeq <msdousti(a)gmail.com> wrote:
>There, they used the result of Sipser: BPP \subseteq NP^NP.
>
>Then, they relativized this using an NP oracle:
>
>BPP^NP \subseteq (NP^NP)^NP.

Ah, I understand your confusion now. When people talk about "relativizing
NP^NP to the oracle C" they mean "NP^(NP^C)" and not "(NP^NP)^C" since
that's the definition that makes sense. "(NP^NP)^C" is not a well-behaved
entity.
--
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 15 Jun 2010 13:13
> Ah, I understand your confusion now.  When people talk about "relativizing
> NP^NP to the oracle C" they mean "NP^(NP^C)" and not "(NP^NP)^C" since
> that's the definition that makes sense.  

I'm afraid that is not the case. Here's a snippet of the
aforementioned paper:
http://i50.tinypic.com/110kqrd.png

As you can see, the base is \Sigma_2 \cap \Pi_2.


>"(NP^NP)^C" is not a well-behaved entity.
Again, I beg to differ. In an earlier post, you said that NP^NP is a
semantic class. I object, since the class has complete problems.
For example, see Section 5.2.2 "Complete problems for levels of PH" of
the following book:

Computational Complexity---A Modern Approach, Sanjeev Arora, Boaz
Barak, Cambridge University Press, 2009.

Here's a snippet:
http://i46.tinypic.com/25p7bki.png



PS: This discussion is very fruitful for me, since I notice things
I've neglected before.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Note on MacLaren and Marsaglia's randomizing by shuffling
Next: semi-Hamiltonian paths in planar triangulations