Re: Questioning the existence of an oracle A whereby P^A =/= NP^A
- From: tchow@xxxxxxxxxxxxx
- Date: 28 May 2007 22:33:48 GMT
In article <1180349092.938328.36920@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Hatem Abdelghani <hatemghani@xxxxxxxxx> wrote:
Well, after thinking for a while, I have fond that the problem with my
way of thinking is that I assume that an Oracle has to be a computable
function. Actually, it doesn't have to be so!!
Ah, yes, that's a good point, which I should have mentioned.
However, I think you're still confused about something.
Comparing the machine A, mentioned in Sipser, by a machine that
accepts prime numbers is wrong.
Of course, it is legitimate to have a language with an infinite number
of strings, but there should be an algorithm that can recognize all
these strings, and that algorithm must be "constructible in finite
time". Such requirement is achieved in the primality test algorithm,
but not in the machine A mentioned in Sipser. I mean, although we have
a definition for the language accepted by A, we don't have a means to
construct the machine A itself in finite time, so we can't assume that
A exists at all.
First of all, just because we don't have a means to construct a machine
in finite time doesn't mean that we can't prove that the machine exists.
For example, there is a famous result of Robertson and Seymour about
graph minors that says that if X is any property of graphs that is closed
under taking minors, then there exists a polynomial time algorithm for
testing the property X. However, the theorem is nonconstructive, and
does not provide any general method for constructing the polynomial-time
machine M for testing X. Nevertheless, M is proven to exist.
The second point is that Sipser *does* in fact show how to construct the
machine A, and the oracle is a computable function in this case (even
though, as you note, it wouldn't have to be for the proof to be correct).
It would indeed be troublesome if Sipser's infinite number of steps were
supposed to be an infinite sequence of steps that *A itself had to execute*.
But that is not the case. The infinite sequence of steps is part of Sipser's
*description* of A, and the crucial question is whether the entity that
he describes is a finite machine that always halts. And the answer is yes.
Although Sipser phrases his decription as an infinite sequence of steps,
he does this for conceptual clarity only---he is not, for example, adding
a new line of code to the computer program at every step.
You might find it a useful exercise to go through the proof again and use
it to write down explicitly a finite computer program that decides the
oracle language in question.
--
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
.
- References:
- Questioning the existence of an oracle A whereby P^A =/= NP^A
- From: Hatem Abdelghani
- Re: Questioning the existence of an oracle A whereby P^A =/= NP^A
- From: tchow
- Re: Questioning the existence of an oracle A whereby P^A =/= NP^A
- From: Hatem Abdelghani
- Questioning the existence of an oracle A whereby P^A =/= NP^A
- Prev by Date: Re: Questioning the existence of an oracle A whereby P^A =/= NP^A
- Next by Date: Graph - find a path from A to B with path constraints
- Previous by thread: Re: Questioning the existence of an oracle A whereby P^A =/= NP^A
- Next by thread: #-3SAT algorithms
- Index(es):
Relevant Pages
|
