About: Compression theorem

An Entity of Type: Abstraction100002137, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In computational complexity theory, the compression theorem is an important theorem about the complexity of computable functions. The theorem states that there exists no largest complexity class, with computable boundary, which contains all computable functions.

Property Value
dbo:abstract
  • In computational complexity theory, the compression theorem is an important theorem about the complexity of computable functions. The theorem states that there exists no largest complexity class, with computable boundary, which contains all computable functions. (en)
  • 圧縮定理（あっしゅくていり、英: compression theorem）は計算複雑性理論における計算可能関数の複雑性に関する重要な定理である。 この定理は計算可能な上限で抑えられる最大の複雑性クラス（それは全ての計算可能関数を含む）が存在しないことを述べる。 (ja)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 2817175 (xsd:integer)
dbo:wikiPageLength
  • 1761 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 998194621 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
gold:hypernym
rdf:type
rdfs:comment
  • In computational complexity theory, the compression theorem is an important theorem about the complexity of computable functions. The theorem states that there exists no largest complexity class, with computable boundary, which contains all computable functions. (en)
  • 圧縮定理（あっしゅくていり、英: compression theorem）は計算複雑性理論における計算可能関数の複雑性に関する重要な定理である。 この定理は計算可能な上限で抑えられる最大の複雑性クラス（それは全ての計算可能関数を含む）が存在しないことを述べる。 (ja)
rdfs:label
  • Compression theorem (en)
  • 圧縮定理 (ja)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License