en>ArmbrustBot: /* See also */re-categorisation per CFDS, replaced: Category:Potential → Category:Potentials using AWB

2013-10-09T14:13:58Z

See also: re-categorisation per CFDS, replaced: Category:Potential → Category:Potentials using AWB

← Older revision		Revision as of 16:13, 9 October 2013
Line 1:		Line 1:
	~~I would like~~ to ~~introduce myself to you, I am Jayson Simcox but I don~~'~~t like when individuals use my full title~~. ~~I am really fond~~ of to go to ~~karaoke but I~~'~~ve been taking on new issues recently. Kentucky is where I~~'~~ve usually been residing~~. ~~Office supervising is what she~~ does for a ~~residing.~~<br><br>~~Here is my webpage; tarot card readings~~ ([~~http~~://~~cartoonkorea~~.~~com~~/~~ce002/1093612 cartoonkorea~~.~~com~~])		In [[computational complexity theory]] '''Blum's speedup theorem''', first stated by [[Manuel Blum]] in 1967, is a fundamental theorem about the complexity of [[computable function]]s.

			Each computable function has an infinite number of different program representations in a given programming language. In the theory of [[algorithm]]s one often strives to find a program with the smallest complexity for a given computable function and a given [[complexity measure]] (such a program could be called ''optimal''). Blum's speedup theorem shows that there are computable functions that have no optimal program for any measure of complexity. This also rules out the idea there is a way to assign to arbitrary functions ''their'' computational complexity, meaning the assignment to any ''f'' of the complexity of an optimal program for ''f''. This does of course not exclude the possibility of finding the complexity of an optimal program for certain specific functions.

			== Speedup theorem ==

			Given a [[Blum complexity measure]] <math>(\varphi, \Phi)</math> and a total computable function <math>f</math> with two parameters, then there exists a total [[computable predicate]] <math>g</math> (a [[boolean valued function\|boolean valued]] computable function) so that for every program <math>i</math> for <math>g</math>, there exists a program <math>j</math> for <math>g</math> so that for [[almost all]] <math>x</math>
			:<math>f(x, \Phi_j(x)) \leq \Phi_i(x) \, </math>

			<math>f</math> is called the '''speedup function'''. 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).

			== See also ==
			* [[Gödel's speed-up theorem]]
			* [[Speedup theorem]]

			== References ==
			* {{cite doi\|10.1145/321386.321395}}
			* Peter van Emde Boas, Ten years of speedup, Proceedings of MFCS (Jirí Becvár, ed.), Lecture Notes in Computer Science, vol. 32, Springer, 1975, pp. 13–29.

			== External links ==
			* {{MathWorld\|title=Blum's Speed-Up Theorem\|urlname=BlumsSpeed-UpTheorem}}

			[[Category:Theorems in computational complexity theory]]

en>Ninly: cl

2012-08-02T14:49:10Z

New page

I would like to introduce myself to you, I am Jayson Simcox but I don't like when individuals use my full title. I am really fond of to go to karaoke but I've been taking on new issues recently. Kentucky is where I've usually been residing. Office supervising is what she does for a residing.<br><br>Here is my webpage; tarot card readings ([http://cartoonkorea.com/ce002/1093612 cartoonkorea.com])

Homoeoid - Revision history

en>ArmbrustBot: /* See also */re-categorisation per CFDS, replaced: Category:Potential → Category:Potentials using AWB

en>Ninly: cl