Re: Can EXPTIME and NP be separated via diagonalization?

On Aug 7, 11:31 am, tc...@xxxxxxxxxxxxx wrote:
In article <dbc7e189-f217-494a-8f7b-1859d0c92...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

<cplxp...@xxxxxxxxx> wrote:
Step 1: Nondeterministically guess an algorithm X that solves the
inputted language in time bounded by x^k+k; or guess that no such
algorithm exists. Now we must verify that the algorithm works.

I think you have a misconception about how nondeterminism works. In
particular it's unclear how you can nondeterministically guess an algorithm
and simultaneously nondeterministically guess that no algorithm exists.

As you yourself say, if you're not worried about the running time, you can
replace nondeterminism by determinism. I think if you try describing your
algorithm purely deterministically, you will see the problem with your
construction.
--
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



Hmmm...yeah, now that I look over my argument again, it doesn't seem
right. It was originally of a different form...I was trying to prove
that if P = NP, then for any fixed natural number k ALGSAT-k is a
member of NP. I couldn't prove that, but I thought I could generalize
the proof to show that ALGSAT-k is decidable. It doesn't seem to work
though.

When I was referring to guessing something or that no such thing
exists, I guess what I was referring to was the notion that an NP
search problem can be solved with an NP oracle. For example, given a
SAT formula, if I have an oracle for SAT, I can find a satisfying
arrangement for the formula or find that no such arrangement exists.
That's what I meant by "guessing the algorithm, or that no algorithm
exists."

Really though, I needed to be more precise in discussing that
argument. I was trying to summarize it and in the process abandoned
all rigor. I guess I was just being sloppy.

Also, here's a point...doesn't the proof that I gave violate Rice's
theorem? (I need to study Rice's theorem a little better before I
start invoking it...but I think it does.)

-Phil



.

Relevant Pages

  • Clarifying nondeterminism
    ... I am having a problem with nondeterminism, and was hoping someone here could ... An archtypical algorithm for solving NP class problems is defined as ... check the certificate; if the certificate works, ...
    (comp.theory)
  • Re: Clarifying nondeterminism
    ... I am having a problem with nondeterminism, and was hoping someone here could ... An archtypical algorithm for solving NP class problems is defined as ... check the certificate; if the certificate works, ... The NDTM model described in Garey and Johnson's "Computers and ...
    (comp.theory)
  • Re: Clarifying nondeterminism
    ... > I am having a problem with nondeterminism, and was hoping someone here could ... > An archtypical algorithm for solving NP class problems is defined as ... > certificate doesn't work, then give up. ... Thus a non-deterministic algorithm like the one you ...
    (comp.theory)
  • Re: Can EXPTIME and NP be separated via diagonalization?
    ... inputted language in time bounded by x^k+k; ... Now we must verify that the algorithm works. ... I think you have a misconception about how nondeterminism works. ...
    (comp.theory)
  • Re: Questioning the existence of an oracle A whereby P^A =/= NP^A
    ... way of thinking is that I assume that an Oracle has to be a computable ... but there should be an algorithm that can recognize all ... in finite time doesn't mean that we can't prove that the machine exists. ... supposed to be an infinite sequence of steps that *A itself had to execute*. ...
    (comp.theory)