Re: Can EXPTIME and NP be separated via diagonalization?

On Aug 5, 10:38 am, tc...@xxxxxxxxxxxxx wrote:
In article <4789ed7d-31a2-45d3-9783-ad37dcb6c...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

<cplxp...@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


I don't think I followed that. How do we obtain a list of all
polynomial time algorithms? Also, how does the zig-zagging give us
the result of an algorithm? How do we verify that the algorithm we've
found solves SAT? What about algorithms with different lengths?
Suppose I have one polytime algorithm that ends after 10 steps...how
do I zigzag beyond that point?

I think I may have been misleading in what I said. I was referring to
the ability to actually find the algorithm that solves SAT by running
a real, deterministic algorithm. I suppose I see what you are saying
(that it's technically possible to produce the algorithm that solves
SAT if such an algorithm exists), even though I don't understand it.

Does that mean that it's impossible for P = NP to be undecidably true--
i.e., impossible for there to be an algorithm that solves SAT that
cannot be proven to solve SAT? If that's true, I had never heard that
before.

-Phil


.

Relevant Pages

  • 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)
  • Re: JSH: Nearly done
    ... my response to your "polynomial time" below.) ... algorithms really are, so I'll tell you: For a factoring algorithm to ... it doesn't hurt to use recursion in a "proof of concept" ...
    (sci.math)
  • Re: Can EXPTIME and NP be separated via diagonalization?
    ... where M is a Turing machine and p is a polynomial ... can be done in polynomial time. ... How do we verify that the algorithm we've found solves SAT? ... Consider, for a fixed integer k, the decision problem ALGSAT-k. ...
    (comp.theory)
  • Re: New algorithm for the isomorphism of graphs
    ... complicated algorithm works better (avoids backtracking entirely, ... indexed variable, assigning a value to a variable, or comparing two ... so, once you "big O" it, you end up with a running time of 1. ... in polynomial time. ...
    (sci.math)