Gap theorem

From Wikipedia, the free encyclopedia

You have new messages (last change).
This article or section is in need of attention from an expert on the subject.
Please help recruit one or improve this article yourself. See the talk page for details.
Please consider using {{Expert-subject}} to associate this request with a WikiProject
See also Gap theorem (disambiguation) for other gap theorems in mathematics.

In computational complexity theory the Gap theorem is an important [citation needed] theorem about the complexity of computable functions. The theorem was proved independently by Boris Trakhtenbrot in 1964 and Allan Borodin in 1972.

The theorem can be proved by using the Blum axioms without any reference to a concrete computational model.

[edit] Gap theorem

Given two total computable functions f and g with

x \leq g(x) \quad (\forall x),

then there exists a total computable function h with

f(x) \leq h(x) \quad (\forall x)

and the complexity classes with boundary function h and g \circ h are identical.

[edit] References

  • A. Borodin, "Computational complexity and the existence of complexity gaps", Journal of the ACM, 19, 158-174, January 1972.
  • B. Trakhtenbrot, "Turing computations with logarithmic delay", Algebra i Logika, 3, 3-48, 1964.
Retrieved from "http://en.wikipedia.org../../../g/a/p/Gap_theorem.html"