Speedup theorem

Speedup theorem

In computational complexity theory, a speedup theorem is a theorem that considers some algorithm solving a problem and demonstrates the existence of a faster algorithm solving the same problem (or more generally, an algorithm using less of any resource, not just time).

The linear speedup theorem for Turing machines proves that given any machine solving a problem using f("n") of some resource, there is another machine that solves the same problem using "c"f("n")+"n"+2 of that resource, where "c" > 0 is arbitrary.

Blum's speedup theorem demonstrates the existence of a problem such that if any algorithm can solve it in time O(f("n")), there is another algorithm that solves it in time O(log f("n")).


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Speedup-Theorem — In der Komplexitätstheorie dienen verschiedene Speedup Theoreme (Beschleunigungssätze) für den Nachweis, dass eine Maschine oder ein Algorithmus um einen gewissen Faktor beschleunigt werden kann, wenn bereits eine andere Maschine oder ein anderer …   Deutsch Wikipedia

  • Speedup Theorem — In der Komplexitätstheorie dienen verschiedene Speedup Theoreme (Beschleunigungssätze) für den Nachweis, dass eine Maschine oder ein Algorithmus um einen gewissen Faktor beschleunigt werden kann, wenn bereits eine andere Maschine oder ein anderer …   Deutsch Wikipedia

  • Blum's speedup theorem — In computational complexity theory Blum s speedup theorem, first stated by Manuel Blum in 1967, is an important theorem about the complexity of computable functions. Each computable function has an infinite number of different program… …   Wikipedia

  • Linear speedup theorem — In computational complexity theory, the linear speedup theorem for Turing machines proves that given any c > 0 and any Turing machine solving a problem in time f( n ), there is another machine that solves the same problem in time c f( n… …   Wikipedia

  • Gap theorem — See also Gap theorem (disambiguation) for other gap theorems in mathematics. In computational complexity theory the Gap theorem is a major theorem about the complexity of computable functions. [Lance Fortnow, Steve Homer,… …   Wikipedia

  • Beschleunigungssatz — In der Komplexitätstheorie dienen verschiedene Speedup Theoreme (Beschleunigungssätze) für den Nachweis, dass eine Maschine oder ein Algorithmus um einen gewissen Faktor beschleunigt werden kann, wenn bereits eine andere Maschine oder ein anderer …   Deutsch Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • Asymptotically optimal — In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly… …   Wikipedia

  • Komplexitätstheorie — Die Komplexitätstheorie als Teilgebiet der Theoretischen Informatik befasst sich mit der Komplexität von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen. Die Komplexität von Algorithmen… …   Deutsch Wikipedia

  • List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”