Re: Can EXPTIME and NP be separated via diagonalization?

In article <dbc7e189-f217-494a-8f7b-1859d0c9292d@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@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
.

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?
    ... Now we must verify that the algorithm works. ... I think you have a misconception about how nondeterminism works. ... 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. ...
    (comp.theory)
  • Re: Why NP Problem is Important and Practical Examples
    ... there is a poly-time algorithm to verify a particular solution. ... My student was working as a software developer and he was meeting ...
    (comp.theory)