Re: Can EXPTIME and NP be separated via diagonalization?

In article <4789ed7d-31a2-45d3-9783-ad37dcb6c77b@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@xxxxxxxxx> wrote:
For example, suppose I could prove that if P = NP, there is an
algorithm that finds an algorithm that solves SAT.

We already know how to write down explicitly an algorithm with the property
that, if P = NP, it solves SAT in polynomial time. Just list all polytime
algorithms and multitask over them all.

In more detail, let A_1, A_2, A_3, ..., be a list of all polytime
algorithms. Draw the following grid:

A_1: step 1, step 2, step 3, step 4, ...
A_2: step 1, step 2, step 3, step 4, ...
A_3: step 1, step 2, step 3, step 4, ...
....

To multitask over all these algorithms, just zigzag your way through this
grid, as in the proof that the rational numbers are countable. If P = NP,
then some specific algorithm---say A_n---will solve SAT in polynomial
time. The multitasking algorithm will basically simulate A_n, while
wasting only a polynomial amount of time trying other algorithms.
--
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

  • Re: Can EXPTIME and NP be separated via diagonalization?
    ... algorithm that finds an algorithm that solves SAT. ... that, if P = NP, it solves SAT in polynomial time. ... grid, as in the proof that the rational numbers are countable. ...  The multitasking algorithm will basically simulate A_n, ...
    (comp.theory)
  • Re: Can EXPTIME and NP be separated via diagonalization?
    ... algorithm that finds an algorithm that solves SAT. ... To multitask over all these algorithms, just zigzag your way through this ... grid, as in the proof that the rational numbers are countable. ... and beyond my knowledge without to modify the original algorithm. ...
    (comp.theory)
  • Re: Can EXPTIME and NP be separated via diagonalization?
    ... algorithm that finds an algorithm that solves SAT. ... that, if P = NP, it solves SAT in polynomial time. ... To multitask over all these algorithms, just zigzag your way through this ...
    (comp.theory)
  • 6P=NP: Proof: Nondeterministic Algorithm
    ... each time the algorithm is run the resulting guess may differ. ... be done in Oor polynomial time. ... verifies x if there exists a certificate y such ... Algorithm A verifies language L if for any string x Î ...
    (sci.math)
  • Re: Aspiring highest-order programmer
    ... > that today's programmers repeat the mistakes of the past because their ... not the algorithm choosen to solve it. ... it means that there is no known polynomial time algorithm to ... algorithm to solve any NP-complete problem, ...
    (comp.programming)