Re: Oracles
- From: jdolan@xxxxxxxxx (James Dolan)
- Date: Thu, 10 Aug 2006 01:27:31 +0000 (UTC)
|in article <1155135834.283581.151270@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
| <matt.zellman@xxxxxxxxx> wrote:
|
|Why are oracles even noteworthy in discussing computational complexity?
|
|Several things I've read sound like the fact that some oracles make
|P=NP and others make P!=NP is a surprising result. I don't see why it
|should be.
|
|If your solution to an NP-complete problem uses an oracle that is for
|a problem that is NP-hard, then it will make P=NP, otherwise,
|P!=NP. The very fact that an oracle makes an NP problem solvable in P
|indicates that the oracle is NP-hard, because you have just reduced
|an NP problem to it in polynomial time.
|
|How is it that even though P!=NP has been proved given the existence
|of certain oracles, it hasn't been recognized that the existence of
|any oracle is bound to move NP closer to P by reducing the total
|complexity of a computation?
|
|If P!=NP given the existence of any oracle, then shouldn't P!=NP,
|period?
i don't really understand this whole general area very well, so don't
take what i'm about to say as in any way authoritative; it's just an
experiment on my part to see whether some very elementary
considerations might account for whatever it is that's bugging you.
np on the face of it is pretty obviously at least as big a class as p
is.
that remains true in the "relative" case; that is,
np-relative-to-a-given-oracle-o ("np_o" for short) is at least as big
as p_o is.
also np_o is at least as big as np, and p_o is at least as big as p.
so introducing an oracle o isn't going to make the new p (that is p_o)
any further away from including the old np than the old p was.
however it might (for all that you and i know) make the new p further
away from including the _new_ np (that is np_o) than the old p was to
including the old np.
using my baby-level intuition that says that "p=np is a lot like
saying that searching can be done as quickly as checking, at least up
to polynomial equivalence", i (wildly) guess that an oracle that just
instantaneously solves any searching problem for which a polynomial
checking algorithm exists is likely to make the new p big enough to
include the new np, because offhand i don't see how the new searching
ability is going to give you any significant extra checking ability.
but maybe in order to get the new np to be vastly and demonstrably
bigger than the new p, you could take o to be some ridiculously
powerful oracle that somehow gives you a whole lot of extra magical
checking ability for way super-polynomial problems.
as i'm writing this i'm realizing all the more how unsure i am about
how all this stuff works, but what the heck, maybe someone can correct
me if i'm way off.
--
jdolan@xxxxxxxxxxxx
.
- References:
- Oracles
- From: matt . zellman
- Oracles
- Prev by Date: ? dealing with errors
- Next by Date: Pension Plan
- Previous by thread: Re: Oracles
- Next by thread: Re: Oracles
- Index(es):
Relevant Pages
|
