Gap theorem
id:
gap-theorem-257-8696530
title:
Gap theorem
text:
In computational complexity theory, the Gap Theorem, also known as the Borodin–Trakhtenbrot Gap Theorem, is a major theorem about the complexity of computable functions. It essentially states that there are arbitrarily large computable gaps in the hierarchy of complexity classes. For any computable function that represents an increase in computational resources, one can find a resource bound such that the set of functions computable within the expanded resource bound is the same as the set compu
brand slug:
wiki
category slug:
encyclopedia
description:
There are arbitrarily large computable gaps in the hierarchy of complexity classes
original url:
https://en.wikipedia.org/wiki/Gap_theorem
date created:
date modified:
2024-01-15T13:48:30Z
main entity:
{"identifier":"Q1314081","url":"https://www.wikidata.org/entity/Q1314081"}
image:
fields total:
13
integrity:
14