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

In article <9fa6347c-db6d-4a78-8296-e47c1fafe112@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@xxxxxxxxx> wrote:
If you're not tired of answering my questions, I have another idea.
Is it possible to require that an oracle take, say, 2 cycles, or 5
billion cycles, to activate it, instead of one cycle, as it works
conventionally?

On paper, you can specify anything you feel like, as long as you're
mathematically precise. The more relevant question is whether doing
so lets you draw any interesting conclusions.

Is there a book or paper or site that discusses oracles in depth, or that
is used in courses to explain this material?

I don't know of any *single* resource that will address all the issues
you're interested in. However, a lot of top researchers teach courses
in complexity theory and post lecture notes online. One more-or-less
random example:

http://people.csail.mit.edu/madhu/ST05

To find out who the top researchers are, you can do some searching with
Google Scholar for relevant research papers (especially those published in
FOCS and STOC), and you'll see a lot of the same names cropping up again
and again. There are also some blogs you may wish to follow, such as
Lance Fortnow's or Scott Aaronson's.

If you want another exercise about oracles to think about, here's Rudich's
"oracle/algorithm paradox." Many people believe that P^NP != NP^NP. That
is, even given an oracle for SAT, deterministic and non-deterministic
polytime machines do not accept the same class of languages. On the other
hand, if there is a polytime *algorithm* for SAT, then it immediately
follows that P^NP = NP^NP = P. How is it that an oracle, which has the
same input/output behavior as a polytime algorithm, can differ from a
polytime algorithm in this way?
--
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
.