| dbo:abstract
|
- En teoria de la complexitat, la jerarquia booleana (també coneguda per BH, de Boolean Hierarchy) és la jerarquia de combinacions booleanes (intersecció, unió i complementació) dels conjunts NP. També es pot descriure com la classe de circuits booleans sobre predicats NP. El col·lapse de la jerarquia booleana implicaria un col·lapse de la jerarquia polinòmica. (ca)
- Die Boolesche Hierarchie ist eine Hierarchie von Komplexitätsklassen, die als boolesche Kombinationen von NP-Problemen gebildet werden. (de)
- The boolean hierarchy is the hierarchy of boolean combinations (intersection, union and complementation) of NP sets. Equivalently, the boolean hierarchy can be described as the class of boolean circuits over NP predicates. A collapse of the boolean hierarchy would imply a collapse of the polynomial hierarchy. (en)
- En informatique théorique, plus précisément en théorie de la complexité, la hiérarchie booléenne (notée BH pour Boolean hierarchy en anglais) est une hiérarchie de classes de complexité obtenues comme combinaisons booléennes (intersections, unions, et passage au complémentaire) de problèmes de décision de NP. Plus précisément, un langage/problème de décision dans la hiérarchie booléenne s'écrit comme une « formule booléenne » où les « variables » sont des langages de NP, par exemple appartient à la hiérarchie booléenne si , , sont des langages de NP. (fr)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4296 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En teoria de la complexitat, la jerarquia booleana (també coneguda per BH, de Boolean Hierarchy) és la jerarquia de combinacions booleanes (intersecció, unió i complementació) dels conjunts NP. També es pot descriure com la classe de circuits booleans sobre predicats NP. El col·lapse de la jerarquia booleana implicaria un col·lapse de la jerarquia polinòmica. (ca)
- Die Boolesche Hierarchie ist eine Hierarchie von Komplexitätsklassen, die als boolesche Kombinationen von NP-Problemen gebildet werden. (de)
- The boolean hierarchy is the hierarchy of boolean combinations (intersection, union and complementation) of NP sets. Equivalently, the boolean hierarchy can be described as the class of boolean circuits over NP predicates. A collapse of the boolean hierarchy would imply a collapse of the polynomial hierarchy. (en)
- En informatique théorique, plus précisément en théorie de la complexité, la hiérarchie booléenne (notée BH pour Boolean hierarchy en anglais) est une hiérarchie de classes de complexité obtenues comme combinaisons booléennes (intersections, unions, et passage au complémentaire) de problèmes de décision de NP. Plus précisément, un langage/problème de décision dans la hiérarchie booléenne s'écrit comme une « formule booléenne » où les « variables » sont des langages de NP, par exemple appartient à la hiérarchie booléenne si , , sont des langages de NP. (fr)
|
| rdfs:label
|
- Jerarquia booleana (ca)
- Boolesche Hierarchie (de)
- Boolean hierarchy (en)
- Hiérarchie booléenne (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
