379:
563:
516:
488:
59:). The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.
541:
347:) can be time-constructible unless it is eventually constant, since there is insufficient time to read the entire input. However,
182:) steps. This definition is slightly less general than the first two but, for most applications, either definition can be used.
20:
568:
441:
392:
67:
There are two different definitions of a time-constructible function. In the first definition, a function
437:
for which the theorem is true. Time-constructible functions are often used to provide such a definition.
395:. They are important because the time hierarchy theorem relies on Turing machines that must determine in
458:
537:
512:
484:
339:
352:
143:)) time (a unary representation may be used instead, since the two can be interconverted in
32:
397:
258:
131:
48:
557:
391:
Time-constructible functions are used in results from complexity theory such as the
433:. To formulate them precisely, it is necessary to have a precise definition for
454:
425:) in that time. Such results are typically true for all natural functions
158:
There is also a notion of a fully time-constructible function. A function
417:) steps. This is, of course, impossible without being able to calculate
440:
Space-constructible functions are used similarly, for example in the
121:
which, given a string 1, outputs the binary representation of
532:
Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim (1988).
453:
This article incorporates material from constructible on
429:
but not necessarily true for artificially constructed
248:
ones, outputs the binary (or unary) representation of
355:
321:, 2) are time- and space-constructible, as long as
481:Computational Complexity: A Conceptual Perspective
373:
483:. Cambridge University Press. pp. 130, 139.
409:)) time whether an algorithm has taken more than
459:Creative Commons Attribution/Share-Alike License
8:
35:to natural numbers with the property that
354:
507:Homer, Steven; Selman, Alan L. (2011).
466:
109:. In the second definition, a function
285:which, given a string 1 consisting of
244:which, given a string 1 consisting of
209:which, given a string 1 consisting of
170:which, given a string 1 consisting of
86:which, given a string 1 consisting of
7:
502:
500:
474:
472:
470:
509:Computability and Complexity Theory
383:is a space-constructible function.
198:if there exists a positive integer
75:if there exists a positive integer
14:
281:if there exists a Turing machine
240:if there exists a Turing machine
166:if there exists a Turing machine
117:if there exists a Turing machine
305:All the commonly used functions
289:ones, halts after using exactly
213:ones, halts after using exactly
564:Computational complexity theory
186:Space-constructible definitions
457:, which is licensed under the
368:
362:
63:Time-constructible definitions
1:
511:(Second ed.). Springer.
337:> 0. No function which is
16:Concept in complexity theory
232:. Equivalently, a function
25:time-constructible function
585:
174:ones, stops after exactly
90:ones, stops after exactly
43:) can be constructed from
279:fully space-constructible
479:Goldreich, Oded (2008).
164:fully time-constructible
534:Structural Complexity I
442:space hierarchy theorem
374:{\displaystyle \log(n)}
393:time hierarchy theorem
375:
190:Similarly, a function
376:
205:and a Turing machine
51:in the time of order
435:a natural function f
353:
256:), while using only
536:. Springer-Verlag.
238:space-constructible
196:space-constructible
82:and Turing machine
569:Types of functions
371:
115:time-constructible
73:time-constructible
518:978-1-4614-0681-5
490:978-0-521-88473-0
273:Also, a function
21:complexity theory
576:
548:
547:
529:
523:
522:
504:
495:
494:
476:
382:
380:
378:
377:
372:
221:) cells for all
98:) steps for all
584:
583:
579:
578:
577:
575:
574:
573:
554:
553:
552:
551:
544:
531:
530:
526:
519:
506:
505:
498:
491:
478:
477:
468:
450:
389:
351:
350:
348:
333:for a constant
303:
231:
204:
188:
108:
81:
65:
33:natural numbers
17:
12:
11:
5:
582:
580:
572:
571:
566:
556:
555:
550:
549:
542:
524:
517:
496:
489:
465:
464:
449:
446:
388:
385:
370:
367:
364:
361:
358:
329:) is at least
302:
299:
229:
202:
187:
184:
106:
79:
64:
61:
49:Turing machine
27:is a function
15:
13:
10:
9:
6:
4:
3:
2:
581:
570:
567:
565:
562:
561:
559:
545:
543:3-540-18622-0
539:
535:
528:
525:
520:
514:
510:
503:
501:
497:
492:
486:
482:
475:
473:
471:
467:
463:
462:
460:
456:
447:
445:
443:
438:
436:
432:
428:
424:
420:
416:
412:
408:
404:
400:
399:
394:
386:
384:
365:
359:
356:
346:
342:
341:
336:
332:
328:
324:
320:
316:
312:
308:
300:
298:
296:
292:
288:
284:
280:
276:
271:
269:
265:
261:
260:
255:
251:
247:
243:
239:
235:
228:
224:
220:
216:
212:
208:
201:
197:
193:
185:
183:
181:
177:
173:
169:
165:
161:
156:
154:
150:
146:
142:
138:
134:
133:
128:
124:
120:
116:
112:
105:
101:
97:
93:
89:
85:
78:
74:
70:
62:
60:
58:
54:
50:
46:
42:
38:
34:
30:
26:
22:
533:
527:
508:
480:
452:
451:
439:
434:
430:
426:
422:
418:
414:
410:
406:
402:
396:
390:
387:Applications
344:
338:
334:
330:
326:
322:
318:
314:
310:
306:
304:
294:
290:
286:
282:
278:
274:
272:
267:
263:
257:
253:
249:
245:
241:
237:
233:
226:
222:
218:
214:
210:
206:
199:
195:
191:
189:
179:
175:
171:
167:
163:
159:
157:
152:
148:
144:
140:
136:
130:
126:
122:
118:
114:
110:
103:
99:
95:
91:
87:
83:
76:
72:
68:
66:
56:
52:
44:
40:
36:
28:
24:
18:
313:) (such as
558:Categories
455:PlanetMath
448:References
270:)) space.
162:is called
155:)) time).
113:is called
71:is called
360:
297:) cells.
301:Examples
381:
349:
540:
515:
487:
129:) in
47:by a
31:from
538:ISBN
513:ISBN
485:ISBN
23:, a
357:log
277:is
236:is
194:is
19:In
560::
499:^
469:^
444:.
331:cn
317:,
225:≥
102:≥
546:.
521:.
493:.
461:.
431:f
427:f
423:n
421:(
419:f
415:n
413:(
411:f
407:n
405:(
403:f
401:(
398:O
369:)
366:n
363:(
345:n
343:(
340:o
335:c
327:n
325:(
323:f
319:n
315:n
311:n
309:(
307:f
295:n
293:(
291:f
287:n
283:M
275:f
268:n
266:(
264:f
262:(
259:O
254:n
252:(
250:f
246:n
242:M
234:f
230:0
227:n
223:n
219:n
217:(
215:f
211:n
207:M
203:0
200:n
192:f
180:n
178:(
176:f
172:n
168:M
160:f
153:n
151:(
149:f
147:(
145:O
141:n
139:(
137:f
135:(
132:O
127:n
125:(
123:f
119:M
111:f
107:0
104:n
100:n
96:n
94:(
92:f
88:n
84:M
80:0
77:n
69:f
57:n
55:(
53:f
45:n
41:n
39:(
37:f
29:f
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.