Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!wuarchive!uunet!mstan!sethb
From: sethb@Morgan.COM (Seth Breidbart)
Newsgroups: comp.theory
Subject: Re: time-constructability of (t(n)^(1/3))
Keywords: time-constructability
Message-ID: <3242@ylum.Morgan.COM>
Date: 8 May 91 17:58:31 GMT
References: <4680@gmdzi.gmd.de>
Organization: Morgan Stanley, & Co., Inc. / New York City, NY
Lines: 29

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