Re: Can EXPTIME and NP be separated via diagonalization?

On Aug 6, 12:04 pm, tc...@xxxxxxxxxxxxx wrote:
In article <1566e937-4569-4a05-9d2c-ded8e2ef3...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

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



Okay, I understand what you were saying now. I think I was misleading
in what I said. I was referring to the possibility of finding an
algorithm that could, if P = NP, actually generate an algorithm that
is guaranteed to solve SAT...in other words, I run algorithm X on
input Y, and the output is the binary encoding of a TM that solves
SAT. Further, if P != NP, this algorithm will fail to return any
algorithm. I have a plan for doing this, although I am not sure if it
is correct. I'll outline it here. (Note, this algorithm definitely
does not run in polynomial time or anything close to it; I only claim
that it runs and halts eventually.)


***

Consider, for a fixed integer k, the decision problem ALGSAT-k. This
decision problem is the question of whether or not a given TM solves a
given language (encoded as a halting DTM) in time bounded by x^k+k.
(I call it ALGSAT to mean basically, "the existence of a satisfying
polynomial time algorithm that solves the language.") So for example,
PRIMES would be in ALGSAT-4 if there exists a Turing machine X that
solves PRIMES (which is represented as a TM, though not necessarily as
a polynomial-time one) in time bounded by x^4+4 or faster. (As you
mentioned, x^k+j, or really even just x^k+k, is an upper bound for
every polynomial.)

Obviously, if we could establish that for some integer k, SAT is a
member of ALGSAT-k, then we would have proven that P = NP.

Now I set about to prove that ALGSAT-k is decidable. Here is the gist
of the algorithm that solves ALGSAT-k for a fixed k:

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.

Step 2: Nondeterministically guess a counterexample Y, in the form of
a string, such that X(Y) either does not halt in time less than |Y|^k
+k or such that the TM associated with the language disagrees with
X(Y) (meaning that X does not accurately solve the language.) This
can clearly be done in polynomial time (with respect to the length of
the counterexample), because we inherit the bounds x^k+k above.
Again, the alternative is that we "guess" that no such counterexample
exists. The length of the shortest such counterexample is bounded
with respect to the combined lengths of the two Turing machines: the
one associated with the language, and X, the one we guessed. This is
simply because there are a finite number of agreement or disagreement
schemes that exist for two TMs of fixed finite length. (If this is
confusing I can explain in more detail.)

Since deterministic machines that run in bounded time can be
substituted for nondeterministic machines that run in bounded time,
the above process yields a determinstic, bounded-time algorithm for
solving any instance of ALGSAT-k, for fixed k. If P = NP, then for
some value of k, the algorithm associated with ALGSAT-k will accept
SAT.

***


Okay, in fairness that did not actually give an algorithm for solving
SAT as I said it would, but it proves the existence of such an
algorithm. This does not imply that P = NP is decidable, however,
because we could always guess a higher value of k if we fail to find a
value of k s.t. SAT is an element of ALGSAT-k, meaning we could never
prove P != NP using this method. However, it does mean (assuming I
made no mistakes) that if P = NP, there exists an algorithm that can
verify that fact.

Any errors in that proof? (Was the explanation clear enough?) To
summarize very briefly: Given a TM for a language,
nondeterministically guess a polytime DTM that solves it in the
appropriate time, then guess a counterexample to that algorithm
working properly to solve the language in polynomial time (and if
there are no such counterexamples, the algorithm works.)

-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: 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)
  • Re: *Quantum Computing* expert Bill Munro
    ... time on a non-deterministic turing machine, but which, in worst case, ... If P == NP, then there exists some algorithm, which, on a deterministic ... solves one of those problems in polynomial time. ...
    (sci.crypt)