| 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
| |
| dbo:wikiPageLength
|
- 1188 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
