LH (complexity) (original) (raw)
En informatique théorique, plus précisément en théorie de la complexité, la hiérarchie en temps logarithmique (LH) est la classe de complexité des problèmes de décision qui décidés par des machines de Turing alternantes, avec accès direct, en temps logarithmique et avec un nombre borné d'alternations. LH correspond à la logique du premier ordre en complexité descriptive et est égale à AC0 uniforme selon la logique du premier ordre.
| Property | Value |
|---|---|
| dbo:abstract | En informatique théorique, plus précisément en théorie de la complexité, la hiérarchie en temps logarithmique (LH) est la classe de complexité des problèmes de décision qui décidés par des machines de Turing alternantes, avec accès direct, en temps logarithmique et avec un nombre borné d'alternations. LH correspond à la logique du premier ordre en complexité descriptive et est égale à AC0 uniforme selon la logique du premier ordre. (fr) In computational complexity, the logarithmic time hierarchy (LH) is the complexity class of all computational problems solvable in a logarithmic amount of computation time on an alternating Turing machine with a bounded number of alternations. It is a particular case of a bounded alternating Turing machine hierarchy. It is equal to FO and to FO-uniform AC0. The th level of the logarithmic time hierarchy is the set of languages recognised by alternating Turing machines in logarithmic time with random access and alternations, beginning with an existential state. LH is the union of all levels. (en) |
| dbo:wikiPageID | 27998286 (xsd:integer) |
| dbo:wikiPageLength | 1188 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1025480552 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:FO_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:Computational_problem dbr:Logarithmic_growth dbr:Alternating_Turing_machine dbc:Complexity_classes dbr:AC0 dbr:Random-access_Turing_machine dbr:Computation_time dbr:Existential_state |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:ComplexityClasses dbt:Comp-sci-theory-stub |
| dct:subject | dbc:Complexity_classes |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| rdfs:comment | En informatique théorique, plus précisément en théorie de la complexité, la hiérarchie en temps logarithmique (LH) est la classe de complexité des problèmes de décision qui décidés par des machines de Turing alternantes, avec accès direct, en temps logarithmique et avec un nombre borné d'alternations. LH correspond à la logique du premier ordre en complexité descriptive et est égale à AC0 uniforme selon la logique du premier ordre. (fr) In computational complexity, the logarithmic time hierarchy (LH) is the complexity class of all computational problems solvable in a logarithmic amount of computation time on an alternating Turing machine with a bounded number of alternations. It is a particular case of a bounded alternating Turing machine hierarchy. It is equal to FO and to FO-uniform AC0. The th level of the logarithmic time hierarchy is the set of languages recognised by alternating Turing machines in logarithmic time with random access and alternations, beginning with an existential state. LH is the union of all levels. (en) |
| rdfs:label | LH (complexité) (fr) LH (complexity) (en) |
| owl:sameAs | freebase:LH (complexity) yago-res:LH (complexity) wikidata:LH (complexity) dbpedia-fr:LH (complexity) https://global.dbpedia.org/id/4qB7J |
| prov:wasDerivedFrom | wikipedia-en:LH_(complexity)?oldid=1025480552&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:LH_(complexity) |
| is dbo:wikiPageDisambiguates of | dbr:LH |
| is dbo:wikiPageRedirects of | dbr:The_logarithmic_time_hierarchy dbr:Logarithmic_time_hierarchy |
| is dbo:wikiPageWikiLink of | dbr:Descriptive_complexity_theory dbr:Alternating_Turing_machine dbr:AC0 dbr:The_logarithmic_time_hierarchy dbr:Random-access_Turing_machine dbr:LH dbr:Logarithmic_time_hierarchy |
| is foaf:primaryTopic of | wikipedia-en:LH_(complexity) |