Boolean hierarchy (original) (raw)
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.
| Property | Value |
|---|---|
| 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 | 36026354 (xsd:integer) |
| dbo:wikiPageLength | 4296 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1048004603 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:Algebra_of_sets dbc:Hierarchy dbr:NP-complete dbr:Complement_(complexity) dbr:CoNP dbr:Intersection_(set_theory) dbr:Hierarchy_(mathematics) dbr:Boolean_circuit dbr:Polynomial_hierarchy dbr:Union_(mathematics) dbr:NP_(complexity_class) |
| dbp:wikiPageUsesTemplate | dbt:Mvar dbt:Short_description dbt:Tmath dbt:ComplexityClasses dbt:Computer_science_stub |
| dct:subject | dbc:Hierarchy |
| gold:hypernym | dbr:Hierarchy |
| rdf:type | dbo:Software |
| 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 | freebase:Boolean hierarchy wikidata:Boolean hierarchy dbpedia-ca:Boolean hierarchy dbpedia-de:Boolean hierarchy dbpedia-fr:Boolean hierarchy https://global.dbpedia.org/id/4aZa5 |
| prov:wasDerivedFrom | wikipedia-en:Boolean_hierarchy?oldid=1048004603&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Boolean_hierarchy |
| is dbo:wikiPageRedirects of | dbr:DP_(complexity) dbr:DP_(class) |
| is dbo:wikiPageWikiLink of | dbr:DP_(complexity) dbr:Juris_Hartmanis dbr:DP_(class) |
| is foaf:primaryTopic of | wikipedia-en:Boolean_hierarchy |