About: PH (complexity)

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia-live.demo.openlinksw.com

Hierarchy of complexity classes between P and PSPACE

Property	Value
dbo:description	多項式時間問題和多項式空間問題之間的複雜度等級層次 (zh) Hierarchie von Komplexitätsklassen zwischen P und PSPACE. (de) hierarkio de komplikoj inter P kaj PSPACE (eo) hierarchy of complexity classes between P and PSPACE (en) Jerarquia de classes de complexitat entre P i PSPACE (ca)
dbo:thumbnail	wiki-commons:Special:FilePath/Polynomial_time_hierarchy.svg?width=300
dbo:wikiPageExternalLink	http://www.cs.princeton.edu/theory/complexity/ http://ovid.cs.depaul.edu/documents/phcom.pdf
dbo:wikiPageWikiLink	dbr:Oracle_machine dbr:Polynomial-time_reduction dbr:Doi:10.1016/0304-3975(76)90061-X dbr:File:Polynomial_time_hierarchy.svg dbr:P_versus_NP_problem dbc:Structural_complexity_theory dbr:Toda's_theorem dbr:Recursively_enumerable_language dbr:NP_(complexity) dbr:PSPACE dbr:EXPTIME dbr:Analytical_hierarchy dbr:Formal_language dbr:Transitive_closure dbr:Arithmetical_hierarchy dbr:Co-NP dbr:Hierarchy_(mathematics) dbr:Albert_R._Meyer dbc:Hierarchy dbr:Christos_Papadimitriou dbr:David_S._Johnson dbr:Computational_complexity_theory dbr:Bounded-error_probabilistic_polynomial dbr:Polynomial dbr:Boolean_satisfiability_problem dbr:Mathematical_logic dbr:Complexity_class dbr:PSPACE-complete dbr:Karp–Lipton_theorem dbr:Alternating_Turing_machine dbr:P_(complexity) dbr:Sipser–Lautemann_theorem dbr:De_Morgan's_laws dbr:Turing_machine dbr:Boolean_function dbr:SO_(complexity) dbr:Exponential_hierarchy dbr:Decision_problem dbr:Larry_Stockmeyer dbr:Polynomial_time dbr:Michael_R._Garey dbr:PH_(complexity) dbr:Analytic_hierarchy dbr:Decidable_language dbr:Circuit_minimization dbr:Arithmetic_hierarchy dbr:Complete_problem dbr:Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness dbr:Quantified_Boolean_formula dbr:Symposium_on_Switching_and_Automata_Theory dbr:TQBF
dbp:wikiPageUsesTemplate	dbt:R_from_symbol dbt:Cite_book dbt:Reflist dbt:ComplexityClasses dbt:No_footnotes dbt:Mvar dbt:R_from_merge dbt:Unordered_list dbt:Unsolved dbt:Tmath dbt:Mathcal dbt:Short_description
dct:subject	dbc:Mathematical_logic_hierarchies dbc:Complexity_classes
gold:hypernym	dbr:Hierarchy
rdfs:label	PH (complexity) (en) Polynomial hierarchy (en) هرمية كثيرة الحدود (ar) Jerarquia polinòmica (ca) Jerarquía polinómica (es) Polynomialzeithierarchie (de) Hiérarchie polynomiale (fr) 多項式階層 (ja) Hierarquia polinomial (pt) Полиномиальная иерархия (ru) Поліноміальна ієрархія (uk) 多項式譜系 (zh)
owl:sameAs	freebase:PH (complexity) yago-res:PH (complexity) wikidata:PH (complexity) dbpedia-de:PH (complexity) dbpedia-fr:PH (complexity) dbpedia-zh:PH (complexity) dbpedia-ja:PH (complexity) dbpedia-pt:PH (complexity) dbpedia-he:PH (complexity) dbpedia-es:PH (complexity) dbpedia-ru:PH (complexity) dbpedia-ca:PH (complexity) dbpedia-ar:PH (complexity) dbpedia-sk:PH (complexity) dbpedia-uk:PH (complexity) dbpedia-global:PH (complexity) dbr:PH (complexity)
prov:wasDerivedFrom	wikipedia-en:Polynomial_hierarchy?oldid=1291172339&ns=0 wikipedia-en:PH_(complexity)?oldid=1284392089&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Complexity-classes-polynomial.svg wiki-commons:Special:FilePath/Polynomial_time_hierarchy.svg
foaf:isPrimaryTopicOf	wikipedia-en:Polynomial_hierarchy wikipedia-en:PH_(complexity)
is dbo:wikiPageRedirects of	dbr:PH_(complexity) dbr:NP^NP dbr:Sigma2p dbr:Polynomial-time_hierarchy dbr:Polynomial_time_hierarchy
is dbo:wikiPageWikiLink of	dbr:BPP_(complexity) dbr:PP_(complexity) dbr:Oracle_machine dbr:Polynomial-time_reduction dbr:List_of_computability_and_complexity_topics dbr:Intersection_number_(graph_theory) dbr:Sigma_(disambiguation) dbr:P_versus_NP_problem dbr:True_quantified_Boolean_formula dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Belief_revision dbr:NP_(complexity) dbr:Graph_isomorphism dbr:Quantum_supremacy dbr:Seinosuke_Toda dbr:Delta dbr:Berman–Hartmanis_conjecture dbr:Descriptive_complexity_theory dbr:Arithmetical_hierarchy dbr:♯P dbr:Presburger_arithmetic dbr:Boolean_circuit dbr:Default_logic dbr:List_of_unsolved_problems_in_computer_science dbr:Hierarchy_(mathematics) dbr:Albert_R._Meyer dbr:NP-easy dbr:Thue_number dbr:Boson_sampling dbr:Pi_(disambiguation) dbr:Lance_Fortnow dbr:Michael_Sipser dbr:Richard_M._Karp dbr:Succinct_game dbr:Boolean_satisfiability_problem dbr:Complexity_class dbr:List_of_complexity_classes dbr:Reduction_(complexity) dbr:Karp–Lipton_theorem dbr:Alternating_Turing_machine dbr:BQP dbr:P_(complexity) dbr:Bounded_quantifier dbr:List_of_mathematical_logic_topics dbr:Structural_complexity_theory dbr:P/poly dbr:Sipser–Lautemann_theorem dbr:Logic_optimization dbr:Limits_of_computation dbr:Closed-world_assumption dbr:Random_self-reducibility dbr:Nerode_Prize dbr:AC0 dbr:Circuits_over_sets_of_natural_numbers dbr:♯P-completeness_of_01-permanent dbr:Richard_Lipton dbr:Exponential_hierarchy dbr:Boolean_hierarchy dbr:Low_(complexity) dbr:Larry_Stockmeyer dbr:Stable_model_semantics dbr:Arthur–Merlin_protocol dbr:Quantum_complexity_theory dbr:S2P_(complexity) dbr:NP/poly dbr:Maximin_share dbr:List_of_unsolved_problems_in_fair_division dbr:Induced_matching dbr:Mahaney's_theorem dbr:Hedonic_game dbr:Indistinguishability_obfuscation dbr:Descriptive_Complexity dbr:PH_(complexity) dbr:NP^NP dbr:Sigma2p dbr:Polynomial-time_hierarchy dbr:Polynomial_time_hierarchy
is foaf:primaryTopic of	wikipedia-en:Polynomial_hierarchy wikipedia-en:PH_(complexity)