Re: question on complexity theorem proposition

On Jun 4, 6:17 am, Jym <Jean-Yves.Moyen+n...@xxxxxxxxxxxx> wrote:
On Thu, 04 Jun 2009 06:16:47 +0200, pngwen <png...@xxxxxxxxx> wrote:
Given deterministic Turing machines A and B, the decision problem
associated with determining whether or not the running time of A is
bounded above by the function associated with B is undecidable.
Assuming that you can execute B to completion, and that the number

Yes, I guess the first assumption to have is that B indeed computes a  
total function. If it is unknown whether B uniformly terminates (ie  
terminates on all input) than of course the property is undecidable.





computed by B is finite, you can decide whether A is bound by B.  If I
am reading your problem correctly, B computes some function (f(n))
yielding a predicted execution time.  If B is a function in standard O
(n) notation, it would represent the total number of computational
steps in the worst case execution of any algorithm of that class with
input size n.

A sketch of a proof of the decidability of the language is:

Given TM A, let c be the initial configuration of A's tape, and let
n=sizeof(c).  Execute TM B on n to get the expected number of steps, f
(n).  Next, construct a TM D which determines if A is bound by B.  D
performs its calculation by simulating A for at most f(n) steps.  If A
accepts or rejects before being executed for f(n) steps, D accepts.
Otherwise, D rejects.  D must always accept or reject in at most f(n)
steps, and as stated before, we are assuming that f(n) is finite,
hence the language is decidable.

Of course, if I'm missing the point of your proposition, that wouldn't
be correct.  In all fairness, I just completed a long drive across TN,
so I think caution about my answer is best!

I guess what your missing is that Phil's property is about unifformly  
bounding A's complexity.
He does not want to know if, given A, B and c, A(c) is computed in less  
than B(sizeof(c)) stepsd, which is indeed decidable, but wants to know if  
given A and b, *for all* c, A(c) is computed in less than B(sizeof(c))  
steps.

This is, I think, undecidable.

Deciding whether a program (TM) computes in polynomial time is undecidable  
(actually, it is even a Sigma_2-complete statement, hence strictly harder  
than the halting problem). Proving that it is undecidable is pretty easy,  
proving Sigma_2 completeness is a bit harder. There is such a proof done  
by Jean-Yves Marion and myself but we still have to finish writing it and  
publish it... (it's a side result in an accepted paper we have to finish  
rewriting).

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.

So, it is impossible to decide whether a TM terminates in polynomial time  
or not *even if one knows that the TM always terminates (already a non RE  
question)* (N uniformly terminates).

Now, back to Phil's question. The above result shows that if B computes a  
polynomial, then deciding whether A's computing time is bounded by B is  
impossible. It is quite easy to adapt the proof for other functions than  
polynomials.

--
Hypocoristiquement,
Jym.- Hide quoted text -

- Show quoted text -

Yes, I meant to say that each function was deterministic and halts on
all inputs...that is an important fact that I omitted, I apologize.

You are also right that I am not interested the question of whether A
finishes its execution in B steps for just one input; I'm interested
in whether or not the machine A finishes execution in time bounded by
B for all possible inputs. This is not as easy to prove.

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? 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?

-Phil
.

Relevant Pages

  • Re: question on complexity theorem proposition
    ... If it is unknown whether B uniformly terminates than of course the property is undecidable. ... Here is the idea of the proof of undecidability: ... So, to sum up, if M terminates, then N's complexity is bounded by a constant, otherwise it is exponential. ... It is quite easy to adapt the proof for other functions than polynomials. ...
    (comp.theory)
  • Re: question on complexity theorem proposition
    ... terminates on all input) than of course the property is undecidable. ... Here is the idea of the proof of undecidability: ... then deciding whether A's computing time is bounded by B is   ... polynomials. ...
    (comp.theory)
  • Re: polynomial diophantines and derivatives ?
    ... non-solutions in one variable of a polynomial diophantine equation. ... Does that undecidability always comes from undecidable polynomial diophantine ... radius of convergeance, and we cant decide wheither or not a potential E ... when you're talking about polynomials in one variable. ...
    (sci.math)
  • Re: polynomial diophantines and derivatives ?
    ... A sequence of integers has property T if all the ... Let that diophantine equation be E. ... Does that undecidability always comes from ... so the polynomials are not restricted to one variable. ...
    (sci.math)
  • Re: polynomial diophantines and derivatives ?
    ... defined without referring to its derivates or the sequence of its n'th ... A sequence of integers has property T if all the elements in that sequence ... Does that undecidability always comes from undecidable polynomial diophantine ... when you're talking about polynomials in one variable. ...
    (sci.math)