[comp.theory] time-constructability of

bartels@gmdzi.gmd.de (Eric Bartels) (05/08/91)

Hi folks ,


I've got a (perhaps silly) question concerning time-
constructability.
The problem is the following:

You are given a time-constructable function t() with

                 t(n) > n log* (n)        /* iterated log */

Is now the function 
			
		a(n) = 	  ceiling( t(n)^(1/3) )

time-constructable without having to calculate the t(n) ? 
( the ceiling of a real number x denotes the smallest integer 
greater or equal to x ). 
I thought some time over this problem, but couldn't find an
easy solution ? Do you know if it's generally possible ?


thanx ,
       Eric




Eric Bartels ,
GMD and Univ. of Bonn

sethb@Morgan.COM (Seth Breidbart) (05/09/91)

In article <4680@gmdzi.gmd.de> bartels@gmdzi.gmd.de (Eric Bartels)
writes:

>You are given a time-constructable function t() with

>                 t(n) > n log* (n)        /* iterated log */

>Is now the function 

>		a(n) = 	  ceiling( t(n)^(1/3) )

>time-constructable without having to calculate the t(n) ? 
>( the ceiling of a real number x denotes the smallest integer 
>greater or equal to x ). 

In general, no.

Let s(n) be a large function which can be computed in time <<s(n)
(e.g. 2^n).  Let f(n) be a 0/1 function that requires time s(n)^0.5 to
compute.  Define t(n) as:

If f(n)=0 then s(n)
else 8*s(n).

Then a(n) is 2^(n/3) when f(n)=0, 2*2^(n/3) when f(n)=1.  Since s(n)
is easy to compute, if you could compute a(n) in time a(n), you could
compute f(n) in time a(n).  But a(n)<s(n)^0.5, so you can't.

Seth		sethb@fid.morgan.com