Prev: Note on MacLaren and Marsaglia's randomizing by shuffling
Next: semi-Hamiltonian paths in planar triangulations
From: tchow on 15 Jun 2010 15:03
In article <d8bd6348-2009-4651-8d2f-d5e8a6d38634(a)c33g2000yqm.googlegroups.com>,
Sadeq <msdousti(a)gmail.com> wrote:
>> 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.

The notation for oracles is terribly confusing. When people write
\Sigma_2 ^ C, they mean \Sigma_2 relativized to the oracle C, which
means NP^(NP^C).

If you think about it more closely, this *has* to be the right way
to define relativization. What are we doing when we relativize a
complexity class anyway? We're assuming that computational entities
have access to a particular oracle. In a relativized world where
access to an oracle C is freely available, what is the meaning of
something like P^NP? It must mean things that you can compute in
polynomial time given access to C and to an NP^C-complete language.
NP^C already contains C so the relativized version of P^NP must be
P^(NP^C). This is the only definition that will let you relativize
arguments smoothly.

>>"(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.

I should have stated this more carefully. NP^NP is a syntactic class,
but the way you were proposing to define (NP^NP)^C was treating it as
a semantic class. You were talking about the class of machines that
recognizes the language NP^NP. This is not a good way to define a class.
--
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
First  |  Prev  | 
Pages: 1 2 3
Prev: Note on MacLaren and Marsaglia's randomizing by shuffling
Next: semi-Hamiltonian paths in planar triangulations