Re: Can EXPTIME and NP be separated via diagonalization?

In article <1566e937-4569-4a05-9d2c-ded8e2ef3428@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@xxxxxxxxx> wrote:
I don't think I followed that. How do we obtain a list of all
polynomial time algorithms?

List all pairs (M, p) where M is a Turing machine and p is a polynomial
with integer coefficients (in fact, it suffices to list polynomials
of the form n^d + c for some nonnegative integers c and d, since any
polynomial is bounded above by a polynomial of the form n^d + c). This
can be done in polynomial time. To simulate (M, p), just simulate M
and exit after p(n) steps, regardless of whether M thinks it's "done"
or not. You will cover all polytime algorithms in this way.

Note that you don't need to generate all of the pairs (M, p) ahead of
time; you can generate them on the fly as you need them.

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?

The zig-zagging is the main idea, but you'll need to add little subroutines
to address these kinds of issues. When one of the programs on the list
terminates, you quickly enter a subroutine to read its output tape and
check to see if the output is a satisfying assignment. If it works then
you terminate; otherwise, you just keep going as if the program had said
"unsatisfiable."

What about algorithms with different lengths?
Suppose I have one polytime algorithm that ends after 10 steps...how
do I zigzag beyond that point?

The steps after the 10th should be interpreted as no-ops, i.e., do nothing
for one clock tick.

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.

Well, what I gave *is* an explicit algorithm that will find a satisfying
assignment in polynomial time if a satisfying assignment exists, provided
P = NP. We could write the C code and compile it today if we wanted to.

It's true that the algorithm as I've described it won't terminate if the
instance is unsatisfiable, and so it is unsatisfactory in that regard.
You could create an infinite family of zig-zaggers, each of which exits
after n^d + c steps for different values of c and d. These would all
definitely run in polynomial time whether the instance is satisfiable
or not, and infinitely many of them would behave correctly. The trouble
is that you wouldn't know which ones of them were behaving correctly...

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?

No, that doesn't follow. It might be that P = NP and the above algorithm
correctly solves SAT, but that we can't prove that. Just because we can
write down the algorithm doesn't mean we can analyze it and determine
whether it correctly solves SAT.
--
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

  • 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)
Quantcast