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.
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - LH (complexité) (fr)
- LH (complexity) (en)
|
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)
|
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
has 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)
|
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage redirect
of | |
is Wikipage disambiguates
of | |
is foaf:primaryTopic
of | |