58:). Blum's speedup theorem shows that for any complexity measure, there exists a computable function such that there is no optimal program computing it, because every program has a program of lower complexity. This also rules out the idea that there is a way to assign to arbitrary functions
368:. The fact that it may be as fast-growing as desired (as long as it is computable) means that the phenomenon of always having a program of smaller complexity remains even if by "smaller" we mean "significantly smaller" (for instance, quadratically smaller, exponentially smaller).
340:
497:
111:
362:
265:
242:
222:
202:
182:
158:
135:
451:
70:. This does of course not exclude the possibility of finding the complexity of an optimal program for certain specific functions.
51:
20:
377:
272:
50:
one often strives to find a program with the smallest complexity for a given computable function and a given
161:
79:
84:
436:
Mathematical
Foundations of Computer Science 1975 4th Symposium, Mariánské Lázně, September 1–5, 1975
138:
43:
431:
394:
36:
419:
402:
42:
Each computable function has an infinite number of different program representations in a given
470:
447:
439:
411:
473:
347:
250:
227:
207:
187:
167:
143:
120:
114:
491:
438:. Lecture Notes in Computer Science. Vol. 32. Springer-Verlag. pp. 13–29.
423:
390:
28:
443:
245:
478:
47:
415:
16:
Rules out assigning to arbitrary functions their computational complexity
395:"A Machine-Independent Theory of the Complexity of Recursive Functions"
32:
62:
computational complexity, meaning the assignment to any
434:(1975). "Ten years of speedup". In Bečvář, Jiřà (ed.).
350:
275:
253:
230:
210:
190:
170:
146:
123:
87:
356:
335:{\displaystyle f(x,\Phi _{j}(x))\leq \Phi _{i}(x)}
334:
259:
236:
216:
196:
176:
152:
129:
105:
164:computable function) so that for every program
137:with two parameters, then there exists a total
8:
66:of the complexity of an optimal program for
498:Theorems in computational complexity theory
349:
317:
292:
274:
252:
229:
209:
189:
169:
145:
122:
86:
7:
314:
289:
97:
14:
106:{\displaystyle (\varphi ,\Phi )}
54:(such a program could be called
21:computational complexity theory
329:
323:
307:
304:
298:
279:
100:
88:
1:
514:
31:in 1967, is a fundamental
474:"Blum's Speed-Up Theorem"
444:10.1007/3-540-07389-2_179
204:, there exists a program
378:Gödel's speed-up theorem
35:about the complexity of
80:Blum complexity measure
358:
336:
261:
238:
218:
198:
178:
154:
131:
107:
25:Blum's speedup theorem
416:10.1145/321386.321395
359:
337:
262:
239:
219:
199:
179:
155:
132:
108:
432:Van Emde Boas, Peter
348:
273:
251:
228:
208:
188:
168:
144:
139:computable predicate
121:
117:computable function
85:
44:programming language
37:computable functions
46:. In the theory of
471:Weisstein, Eric W.
403:Journal of the ACM
354:
332:
257:
234:
214:
194:
174:
150:
127:
103:
52:complexity measure
27:, first stated by
453:978-3-540-07389-5
357:{\displaystyle f}
260:{\displaystyle x}
237:{\displaystyle g}
217:{\displaystyle j}
197:{\displaystyle g}
177:{\displaystyle i}
153:{\displaystyle g}
130:{\displaystyle f}
505:
484:
483:
457:
427:
399:
366:speedup function
363:
361:
360:
355:
341:
339:
338:
333:
322:
321:
297:
296:
266:
264:
263:
258:
243:
241:
240:
235:
223:
221:
220:
215:
203:
201:
200:
195:
183:
181:
180:
175:
159:
157:
156:
151:
136:
134:
133:
128:
112:
110:
109:
104:
513:
512:
508:
507:
506:
504:
503:
502:
488:
487:
469:
468:
465:
454:
430:
397:
389:
386:
374:
346:
345:
313:
288:
271:
270:
249:
248:
226:
225:
206:
205:
186:
185:
166:
165:
142:
141:
119:
118:
83:
82:
76:
74:Speedup theorem
17:
12:
11:
5:
511:
509:
501:
500:
490:
489:
486:
485:
464:
463:External links
461:
460:
459:
452:
428:
410:(2): 322–336.
385:
382:
381:
380:
373:
370:
364:is called the
353:
343:
342:
331:
328:
325:
320:
316:
312:
309:
306:
303:
300:
295:
291:
287:
284:
281:
278:
256:
233:
213:
193:
173:
162:boolean valued
149:
126:
102:
99:
96:
93:
90:
75:
72:
15:
13:
10:
9:
6:
4:
3:
2:
510:
499:
496:
495:
493:
481:
480:
475:
472:
467:
466:
462:
455:
449:
445:
441:
437:
433:
429:
425:
421:
417:
413:
409:
405:
404:
396:
392:
388:
387:
383:
379:
376:
375:
371:
369:
367:
351:
326:
318:
310:
301:
293:
285:
282:
276:
269:
268:
267:
254:
247:
231:
211:
191:
171:
163:
147:
140:
124:
116:
94:
91:
81:
73:
71:
69:
65:
61:
57:
53:
49:
45:
40:
38:
34:
30:
26:
22:
477:
435:
407:
401:
391:Blum, Manuel
365:
344:
244:so that for
77:
67:
63:
59:
55:
41:
24:
18:
29:Manuel Blum
384:References
246:almost all
48:algorithms
479:MathWorld
315:Φ
311:≤
290:Φ
98:Φ
92:φ
492:Category
424:15710280
393:(1967).
372:See also
78:Given a
56:optimal
33:theorem
450:
422:
113:and a
420:S2CID
398:(PDF)
115:total
60:their
448:ISBN
224:for
184:for
440:doi
412:doi
160:(a
19:In
494::
476:.
446:.
418:.
408:14
406:.
400:.
39:.
23:,
482:.
458:.
456:.
442::
426:.
414::
352:f
330:)
327:x
324:(
319:i
308:)
305:)
302:x
299:(
294:j
286:,
283:x
280:(
277:f
255:x
232:g
212:j
192:g
172:i
148:g
125:f
101:)
95:,
89:(
68:f
64:f
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.