gap theorem (Q1314081)
Jump to navigation
Jump to search
theorem that there are arbitrarily large computable gaps in the hierarchy of complexity classes
- Borodin-Trakhtenbrot gap theorem
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | gap theorem |
theorem that there are arbitrarily large computable gaps in the hierarchy of complexity classes |
|
Statements
Identifiers
1 reference
Sitelinks
Wikipedia(5 entries)
- dewiki Lückensatz von Borodin
- enwiki Gap theorem
- jawiki ギャップ定理 (計算複雑性理論)
- ptwiki Teorema do intervalo
- zhwiki 間隙定理