Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!uunet!math.fu-berlin.de!mailgzrz!opal!unido!gmdzi!bartels
From: bartels@gmdzi.gmd.de (Eric Bartels)
Newsgroups: comp.theory
Subject: time-constructability of (t(n)^(1/3))
Summary: question
Keywords: time-constructability
Message-ID: <4680@gmdzi.gmd.de>
Date: 8 May 91 09:23:32 GMT
Organization: GMD, St. Augustin, F.R. Germany
Lines: 31


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