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


Wait, one more thing.

If it's possible to say that X^A != X^B --> A != B, why doesn't
someone do this to prove P != NP....

Consider some complexity class X, maybe P. Let Q be the oracle from
Baker-Gill-Solovay's proof s.t. P^Q != NP^Q. Then let A equal the
union of every oracle for every language in P, unioned with Q, and let
B be the union of every oracle for every language in NP, also unioned
with Q. The effect is...

A = (U (oracle for x) x is an element of P) U oracle for Q
B = (U (oracle for x) y is an element of NP) U oracle for Q.

Then consider X^A and X^B. Then since the complexity class X has
access to an oracle for all languages in P plus an oracle for Q, X^A
should be something comparable to the language from Baker-Gill-
Solovay, except probably with a few extra languages thrown in, since
the Q oracle could be applied at any time. The other language should
be different from this one.

That's obviously far from a real proof...but I guess what I'm asking
is, is there some reason why that approach couldn't work?

-Phil

.

Relevant Pages

  • M as an implementation language
    ... M encounters the same final problems like assembler language did 30 years ... The solution was not to use assembler directly as a programming language ... even companies like oracle and MS are looking for a way out of it. ... Many M pro's use DOM's, but the theory and basics still not well founded, ...
    (comp.lang.mumps)
  • Re: Paper - impossible to prove P=?NP
    ... deterministic Turing machine with an oracle for A in polynomial time; ... The difference from "real" Turing machines is that ... Then there exists a language A for which P^A = NP^A, ... So techniques for deciding P=?NP would have to be rather deeply ...
    (sci.crypt)
  • Re: obvious ("dumb") question about oracles and P vs. NP
    ... B be the union of every oracle for every language in NP, ... But every string is in *some* polytime language, ...
    (comp.theory)
  • Re: [Info-ingres] Re: What animal should Ingres be?
    ... A more 'full' language would simply allow for code more comprehensible for most of our devs. ... Some are starting to use Java so they can move their stored procs between Oracle and DB2 without translation. ... Ingres could be added to this list. ...
    (comp.databases.ingres)
  • Re: Bug tracking system recommendation
    ... run on Linux and uses either MySQL or Oracle. ... It doesn't matter too much what language it's written in, though either Java or something that doesn't require an interpreter would be preferred over Perl or PHP. ...
    (comp.lang.java.programmer)