Re: obvious ("dumb") question about oracles and P vs. NP

In article <45250138-976c-4c77-9a41-a55759f05709@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@xxxxxxxxx> wrote:
Ok, so what you are saying is that P and NP become not equal when the
model of computation is changed, because of how P and NP are defined?

Right. I'm not sure about your mouse/rodent analogy, though.

Maybe a better analogy is this. I have two different machines A and B,
and they appear to produce identical widgets, but by very different
mechanisms. Now I go in to both machines and change every gear of type X
to a gear of type Y. The effect of this is unpredictable. In particular,
it doesn't follow that the modified machines will continue to produce the
same widgets. There may be a lot more gears of type X in machine A, for
example, and they might serve very different functions in the two machines.

Is that about right? Also, do you think it might make sense to
reverse the notation? E.g., say "B^P != B^NP," because what you've
really done is allowed an oracle machine to enter the model of
computation, and then examined the complexity classes under the new
model.

If what you mean to say is that P^A is not necessarily equal to P^B
if A and B are different oracles, then certainly this is true.

Here's one final question. Would it be possible to prove P != NP if
someone could find somehow prove that X^A != X^B, where X is some
complexity class, and A and B are two oracles that would be equivalent
(somehow) if P = NP? In other words, does X^A != X^B imply A != B?

Yes, this is correct.
--
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
.

Relevant Pages

  • Re: obvious ("dumb") question about oracles and P vs. NP
    ... Now I go in to both machines and change every gear of type X ... if A and B are different oracles, ... complexity class, and A and B are two oracles that would be equivalent ...
    (comp.theory)
  • Re: 3 phase?
    ... It's just the installation cost I'm concerned about. ... I may only have a couple of possible 3phase machines. ... The equipment is more expensive, but not solid gold expensive - 600V ... Class gear is roughly double the same stuff for 300V ...
    (rec.crafts.metalworking)
  • Re: obvious ("dumb") question about oracles and P vs. NP
    ... X = the class of all languages that are decided by machines that ... behave in the precise manner X ... where A, B, C, D, are oracles machines, and X has access to all of them? ... oracles in a fixed manner, and let the oracle A vary. ...
    (comp.theory)
  • Re: K&T Parts
    ... The shop is run as a production shop where a high machinst skill level is not necessary. ... Cutting a spur gear is not that hard if you have a dividing head. ... Spline cutting on a shaft is also very easy to do with the dividing head. ... On the K&T and Cincinatti manual machines the hardest part to make is the clutch plates. ...
    (rec.crafts.metalworking)
  • Re: Mazak recall?
    ... Over 100 machines were shipped with soy sauce instead of gear ... Multiplex, etc. are built in Japan. ...
    (alt.machines.cnc)