Re: question on complexity theorem proposition

On Jun 4, 3:36 pm, Jym <Jean-Yves.Moyen+n...@xxxxxxxxxxxx> wrote:
On Thu, 04 Jun 2009 14:51:54 +0200, <cplxp...@xxxxxxxxx> wrote:
Deciding whether a program (TM) computes in polynomial time is  
undecidable  
Here is the idea of the proof of undecidability :
* Let P be a polynomial and M be a TM.
* Build the TM N as follows :
_ on input x, N simulates M on input 0 for at most 2^x (or 2^|x|) steps.
_ If M terminates in less than 2^x steps, then N stops immediately and  
returns the result of M.
_ otherwise, N returns anything (eg reject the input).

Now, what is the running time of N ? Well, there are two cases :
1/ M terminates in S steps. Then N runs for at most 2^S steps (plus  
simulation overhead) which is a constant.
2/ M does not terminates. Then N always run for 2^X steps on input x.

So, to sum up, if M terminates, then N's complexity is bounded by a  
constant, otherwise it is exponential.

N is polynomial <=> M teminates.
I am not sure that I followed your proof.  What is "input 0" in your
proof?  Just the string "0" inputted to the TM M?

Actually any fixed input works. The proof rely on the fact that it is  
impossible to decide whether a TM halts on any given input (Turing's  
original result). Here, I chose the input "0", but any other input you'd  
like works, as long as it is always the same you use.

And what
relationship does N have to proving the undecidability of the decision
problem associated with whether or not an algorithm runs in polynomial
time?  Could you explain your proof in more depth?

N simulates M but with an internal time bound so it is assured to stop  
(either because M stops in the given time or because the time is  
exhausted).

The time bound for the simulation grows (exponentially) with the (size of  
the) input of N.

If M terminates (on the fixed input chosen for M), then since the time  
bound for the simulation increase, there is a point when the simulation  
have enough time to go all the way to the termination. If M doesn't  
terminate, then no matter what the time bound is, N will always stop  
because it is exhausted (never because the simulation is over since the  
simulation can be over).

So, if M terminates, the time needed for the computation of N is bounded  
by a constant : the time necessary to simulate M until it ends. Either the  
input is two small and N halts because of the exhausion of the time bound,  
but this happens in less time than what is needed to simulate M until the  
end, or the time bound is large enough and N halts when the simulation  
halts, after the time necessary to do the simulation (the bound above).

On the other hand, if M doesn't terminates, then N always exhausts the  
time bound and the bound is computed so that it means that N runs for an  
exponential time.

Which gives the final equivalence :
N is polynomial <=> M terminates.

Now, what I haven't explicitely mention to close the proof goes as follows:
If we where able to decide whether a given TM has polynomial complexity,  
then we would be able to solve the HALTing problem using this reduction.  
Given a TM M, build the corresponding TM N, feed N to the decision  
procedure of polynomial time. The answer of this procedure is also the  
answer to the termination of M.
Since we know (Turing) that the HALT is undecidable, then so is the  
polynomial bound. (standard reduction technique for prooving  
undecidability result)

--
Hypocoristiquement,
Jym.

OK, I've re-read your posts a few times, and I think I understand your
argument.

You're saying: Assume there exists an algorithm

C(TM A)

such that C returns true iff A runs in polynomial time. Then you say,
we construct an algorithm that solves the halting problem; call it W:

W( TM A, string S)
{
Construct the algorithm below:

//start constructed algorithm

B(int x)
{
for (int i = 0; i < 2^x; i++)
{
execute one step of A(S); //note that A is hardcoded into
this construction, not inputted
if (A has finished executing)
return the final result of A's execution on 0;
}
return false;
}

//end constructed algorithm


return C(B);


}


Obviously we cannot solve the halting problem, so the existence of
this algorithm proves that we cannot algorithmically test for
polynomial-time execution of algorithms.

Now that I've written it out and thought about it for a few minutes, I
believe you that this works; that's very clever and very similar to
the logic of Rice's theorem.

My proof was along rather different lines, but I have to admit that I
like your proof better due to its simplicity.

Thanks for sharing your proof.

-Phil
.

Relevant Pages

  • Re: question on complexity theorem proposition
    ... 2/ M does not terminates. ... The time bound for the simulation grows with the (size of   ... Assume there exists an algorithm ... polynomial-time execution of algorithms. ...
    (comp.theory)
  • P6 = NP (WAS: an oracle paradox)
    ... theory is the Turing machine,introduced by Alan Turing in 1936 ... solvable by some algorithm within anumber of steps bounded by some xed ... over .Then a language over is a subset L of. ... We say that R is polynomial-time i LR ...
    (sci.math)
  • 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)
  • Re: Math errors in book Secret Life of Numbers
    ... his students have proven that primes can be found in polynomial time. ... For practical purposes the algorithm is, admittedly, still too ... that in practice, it always was solved in polynomial time using the ... the simplex method is not a polynomial-time algorithm. ...
    (sci.math.research)