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 computable within the original bound.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Lückensatz von Borodin (de)
- Gap theorem (en)
- ギャップ定理 (計算複雑性理論) (ja)
- Teorema do intervalo (pt)
- 間隙定理 (zh)
|
| rdfs:comment
| - ギャップ定理（ギャップていり、英: Gap theorem）またはボロディン-トラクテンブロートのギャップ定理は計算可能関数の複雑性に関する重要な定理である。 これは本質的にはいくらでも大きな計算可能なギャップが複雑性クラスの階層に存在することを示している。計算資源の増加を表現する任意の計算可能関数 に対して、関数 を求めて、-制限計算可能な関数の集合と -制限計算可能関数の集合が一致するようにできる。 この定理はとによって独立に示された。 (ja)
- 在計算複雜性理論，間隙定理，又稱鮑羅丁－特拉赫堅布羅特間隙定理，為與可计算函数複雜度有關的重要定理。 定理斷言，复杂性类的層階之間，有任意大的可計算間隙。意思是，若給定任意一個可計算函數，表示計算資源增加一次的效果，則必能找到某個資源上限，使得即使將資源上限增加一次變成，也無法計算更多函數。 定理由和分別獨立證出。 雖然特拉赫堅布羅特的推導比鮑羅丁早幾年，但時值冷戰，該定理直到鮑羅丁發表後才為西方認識。 (zh)
- Der Lückensatz von Borodin ist ein 1972 von Allan Borodin veröffentlichter Satz der Komplexitätstheorie in der theoretischen Informatik. Der Satz wurde schon 1964 von Boris Trakhtenbrot bewiesen, was aber im Westen unbeachtet blieb. Er besagt, dass es in der Hierarchie von Komplexitätsklassen beliebig große Lücken gibt. Formal:Für totale, berechenbare Funktionen mit , gibt es immer eine totale und berechenbare Funktion sodass gilt: (de)
- 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 computable within the original bound. (en)
- Na teoria da complexidade computacional o teorema do intervalo é um importante teorema sobre a complexidade de funções computáveis. O teorema afirma que, essencialmente, existem grandes intervalos computáveis na hierarquia das classes de complexidade. Para qualquer função computável que represente um aumento em , pode-se encontrar um limite do recurso tal que o conjunto das funções computáveis dentro do limite do recurso expandido é o mesmo que o conjunto das computáveis dentro do limite original. (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - Der Lückensatz von Borodin ist ein 1972 von Allan Borodin veröffentlichter Satz der Komplexitätstheorie in der theoretischen Informatik. Der Satz wurde schon 1964 von Boris Trakhtenbrot bewiesen, was aber im Westen unbeachtet blieb. Er besagt, dass es in der Hierarchie von Komplexitätsklassen beliebig große Lücken gibt. Formal:Für totale, berechenbare Funktionen mit , gibt es immer eine totale und berechenbare Funktion sodass gilt: Obige Funktion kann nicht zeitkonstruierbar sein, sonst wäre dies ein Widerspruch zu den Hierarchiesätzen, welche aussagen, dass eine Erhöhung von Zeit bzw. Platz für eine Berechnung auch eine Erhöhung der Komplexitätsklasse ergibt. (de)
- 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 computable within the original bound. The theorem was proved independently by Boris Trakhtenbrot and Allan Borodin.Although Trakhtenbrot's derivation preceded Borodin's by several years, it was not known nor recognized in the West until after Borodin's work was published. (en)
- ギャップ定理（ギャップていり、英: Gap theorem）またはボロディン-トラクテンブロートのギャップ定理は計算可能関数の複雑性に関する重要な定理である。 これは本質的にはいくらでも大きな計算可能なギャップが複雑性クラスの階層に存在することを示している。計算資源の増加を表現する任意の計算可能関数 に対して、関数 を求めて、-制限計算可能な関数の集合と -制限計算可能関数の集合が一致するようにできる。 この定理はとによって独立に示された。 (ja)
- Na teoria da complexidade computacional o teorema do intervalo é um importante teorema sobre a complexidade de funções computáveis. O teorema afirma que, essencialmente, existem grandes intervalos computáveis na hierarquia das classes de complexidade. Para qualquer função computável que represente um aumento em , pode-se encontrar um limite do recurso tal que o conjunto das funções computáveis dentro do limite do recurso expandido é o mesmo que o conjunto das computáveis dentro do limite original. O teorema foi inicialmente descoberto e provado por Boris Trakhtenbrot em 1964, que o publicou em russo e como resultado, recebeu pouca atenção na época da Guerra Fria. Oito anos mais tarde, o mesmo teorema foi publicado por em 1972 em inglês e recebeu grande atenção, e como resultado, foi chamado de teorema do intervalo de Borodin. (pt)
- 在計算複雜性理論，間隙定理，又稱鮑羅丁－特拉赫堅布羅特間隙定理，為與可计算函数複雜度有關的重要定理。 定理斷言，复杂性类的層階之間，有任意大的可計算間隙。意思是，若給定任意一個可計算函數，表示計算資源增加一次的效果，則必能找到某個資源上限，使得即使將資源上限增加一次變成，也無法計算更多函數。 定理由和分別獨立證出。 雖然特拉赫堅布羅特的推導比鮑羅丁早幾年，但時值冷戰，該定理直到鮑羅丁發表後才為西方認識。 (zh)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)