Re: Fortnow's paper regarding the status of the P vs. NP problem

In article <slrnhf6t1v.n6v.tim@xxxxxxxxxxxxxxxxxxxxxxxxxx>,
Tim Little <tim@xxxxxxxxxxxxxxxxxx> wrote:
The biggest obstacle is that verifying that an algorithm runs in
polynomial time is not in general an operation that can be conducted
in polynomial time. It is not even computable whether it returns a
result at all.

Technically, you are correct, but this is not actually a serious obstacle.
One can restrict to Turing machines that are "polynomially clocked"; that
is, the operating system forces the algorithm to stop after n^3 steps (or
whatever polynomial you want) and outputs "no" if the algorithm hasn't
made up its mind yet by then. Any polynomial-time algorithm that is
computable by a Turing machine is also computable by a polynomially clocked
Turing machine, and for polynomially clocked machines we don't have any
undecidability problems.

Basically, Phil, your intuition is sound, and if Fortnow writes back, there
is a good chance that he will just say what you've already said. The idea
goes all the way back to Goedel's "lost" letter to von Neumann, in which he
pointed out that one can circumvent the undecidability of theoremhood by
putting a bound on the length of the proof we're willing to search for.
Then the problem becomes an NP-complete problem.
--
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

  • P Versus NP
    ... determine whether every language accepted by some nondeterministic ... algorithm in polynomial time is also accepted by some ... L = Lfor some Turing machine M which runs in polynomial time} The ... We say that R is polynomial-time iff L R ...
    (sci.math)
  • Re: Mr. P and Ms. S
    ... determine whether every language accepted by some nondeterministic ... algorithm in polynomial time is also accepted by some ... L = Lfor some Turing machine M which runs in polynomial time} The ... We say that R is polynomial-time iff L R ...
    (sci.math)
  • Classical Proof
    ... MARTIN M. MUSATOV ... and polynomial time achievement. ... Nondeterministic Polynomial-Time ... Turing machine, or a computer program with unbounded memory) which is ...
    (sci.math)
  • Re: michelson morley experiment questions
    ... Turing machine, or a computer program with unbounded memory) which is ... all languages which can be decided by a deterministic polynomial-time ... use the concept of certificate and verifier. ... Two notions of reduction from problem A to problem B are usually ...
    (sci.math)
  • Re: random number generation & predictability
    ... >> Truly unpredictable sequences of numbers can be produced ... No purely deterministic algorithm (without any ... pass all polynomial-time statistical tests *if* there is no polynomial-time ... polynomial time (and of course, they can theoretically be done in polynomial ...
    (comp.theory)