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

In article <126980d5-6bcf-4be7-9e47-7ac496906d8b@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@xxxxxxxxx> wrote:
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.

I'm not sure what you mean by taking the union of two oracles. Oracles are
normally defined by specifying a language (the oracle tells you whether a
given string is or is not in the language). By the union of two oracles,
do you mean the oracle obtained by taking the union of the languages in
question? But every string is in *some* polytime language, so taking the
union of all languages in P gives you the set of all strings. Or are you
trying to create a machine that has access to a bunch of different oracles
rather than just one oracle?
--
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

  • 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: [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)
  • Re: extracting data from a database and converting it into an XML file
    ... Because you don't really have a C or C++ LANGUAGE ... What you need is an Oracle DB library and an XML-parser library. ... Oracle and XML programming respectively. ... >> Frank Schmitt ...
    (comp.lang.cpp)