Polynomial hierarchy (original) (raw)
في نظرية التعقيد القسم PH هو قسم كل اللغات في هرم متعدد الحدود (Polynomial hierarchy)، وهذا القسم يشمل جزء لا بأس به من الاقسام المعروفة مثل: NP ,co-NP ... وله عدة تعريفات متكافئة.
| Property | Value |
|---|---|
| dbo:abstract | في نظرية التعقيد القسم PH هو قسم كل اللغات في هرم متعدد الحدود (Polynomial hierarchy)، وهذا القسم يشمل جزء لا بأس به من الاقسام المعروفة مثل: NP ,co-NP ... وله عدة تعريفات متكافئة. (ar) En teoria de la complexitat, la jerarquia polinòmica (de vegades dita jerarquia de temps polinòmic) és una jerarquia de classes de complexitat que generalitza les classes P, NP i co-NP a màquines oracle. És una contrapartida amb recursos fitats de la jerarquia aritmètica i la de lògica matemàtica. (ca) Die Polynomialzeithierarchie (PH, auch: polynomielle Hierarchie) ist die vermutete Struktur von Komplexitätsklassen zwischen NPund PSPACE. Der Grundgedanke hinter der Polynomialzeithierarchie ist die Frage, ob durch die Hinzunahme von Orakeln die Leistungsfähigkeit einer Turingmaschine gesteigert werden kann. (de) En teoría de complejidad computacional, la jerarquía polinómica (a veces llamada jerarquía de tiempo polinómico) es una jerarquía de clases de complejidad que generaliza las clases P, NP y co-NP a máquinas de oráculo. Es una contrapartida de recurso-acotado a la jerarquía aritmética y jerarquía analítica de la lógica matemática. (es) En théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP. La classe PH est l'union de toutes les classes de la hiérarchie polynomiale. (fr) In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH. Classes within the hierarchy have complete problems (with respect to polynomial-time reductions) which ask if quantified Boolean formulae hold, for formulae with restrictions on the quantifier order. It is known that equality between classes on the same level or consecutive levels in the hierarchy would imply a "collapse" of the hierarchy to that level. (en) 多項式階層（たこうしきかいそう、英: Polynomial hierarchy）は、計算量理論における計算量の階層であり、神託機械を使って P、NP、co-NP を一般化させて定義されるものである。 (ja) No ramo da Complexidade computacional a hierarquia polinomial é a hierarquia das Classes de complexidade que generaliza as classes P, NP e Co-NP para Máquinas oráculo. É uma contrapartida limitada de recursos para a Hierarquia aritmética e Hierarquia analítica da Lógica matemática. (pt) 计算复杂度理论中，多项式谱系是一个复杂度系列。它从P、NP和反NP复杂度类逐级产生至预言机。它类似于数理逻辑中算数阶层和，只不过是由逐级放宽资源限制而产生的。 (zh) В теории сложности полиномиальная иерархия — это иерархия классов сложности, которая обобщает классы P, NP, co-NP до вычислений с оракулом. (ru) У теорії складності поліноміальна ієрархія — це ієрархія класів складності, яка узагальнює класи P, NP, co-NP до обчислень з оракулом. (uk) |
| 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:wikiPageID | 658651 (xsd:integer) |
| dbo:wikiPageLength | 15799 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1111112196 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:Bounded-error_probabilistic_polynomial dbr:David_S._Johnson dbr:De_Morgan's_laws dbr:Decision_problem dbr:PSPACE-complete dbr:Analytical_hierarchy dbc:Hierarchy dbr:Mathematical_logic dbr:Oracle_machine dbr:Christos_Papadimitriou dbr:Co-NP dbr:Symposium_on_Switching_and_Automata_Theory dbr:Arithmetical_hierarchy dbc:Structural_complexity_theory dbr:Complexity_class dbr:Computational_complexity_theory dbr:PH_(complexity) dbr:P_(complexity) dbr:Transitive_closure dbr:Circuit_minimization dbr:Larry_Stockmeyer dbr:Polynomial-time_reduction dbr:Recursively_enumerable_language dbr:Albert_R._Meyer dbr:EXPTIME dbr:Alternating_Turing_machine dbr:PSPACE dbr:Formal_language dbr:Toda's_theorem dbr:Karp–Lipton_theorem dbr:Hierarchy_(mathematics) dbr:Boolean_function dbr:Boolean_satisfiability_problem dbr:Polynomial dbr:Polynomial_time dbr:Turing_machine dbr:SO_(complexity) dbr:Exponential_hierarchy dbr:Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness dbr:P_versus_NP_problem dbr:Sipser–Lautemann_theorem dbr:Analytic_hierarchy dbr:Arithmetic_hierarchy dbr:Quantified_Boolean_formula dbr:Michael_R._Garey dbr:Decidable_language dbr:Complete_problem dbr:TQBF dbr:Doi:10.1016/0304-3975(76)90061-X dbr:File:Polynomial_time_hierarchy.svg |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Mvar dbt:No_footnotes dbt:Reflist dbt:Short_description dbt:Tmath dbt:Unordered_list dbt:Mathcal dbt:ComplexityClasses dbt:Unsolved |
| dct:subject | dbc:Hierarchy dbc:Structural_complexity_theory |
| gold:hypernym | dbr:Hierarchy |
| rdf:type | dbo:Software yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| rdfs:comment | في نظرية التعقيد القسم PH هو قسم كل اللغات في هرم متعدد الحدود (Polynomial hierarchy)، وهذا القسم يشمل جزء لا بأس به من الاقسام المعروفة مثل: NP ,co-NP ... وله عدة تعريفات متكافئة. (ar) En teoria de la complexitat, la jerarquia polinòmica (de vegades dita jerarquia de temps polinòmic) és una jerarquia de classes de complexitat que generalitza les classes P, NP i co-NP a màquines oracle. És una contrapartida amb recursos fitats de la jerarquia aritmètica i la de lògica matemàtica. (ca) Die Polynomialzeithierarchie (PH, auch: polynomielle Hierarchie) ist die vermutete Struktur von Komplexitätsklassen zwischen NPund PSPACE. Der Grundgedanke hinter der Polynomialzeithierarchie ist die Frage, ob durch die Hinzunahme von Orakeln die Leistungsfähigkeit einer Turingmaschine gesteigert werden kann. (de) En teoría de complejidad computacional, la jerarquía polinómica (a veces llamada jerarquía de tiempo polinómico) es una jerarquía de clases de complejidad que generaliza las clases P, NP y co-NP a máquinas de oráculo. Es una contrapartida de recurso-acotado a la jerarquía aritmética y jerarquía analítica de la lógica matemática. (es) En théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP. La classe PH est l'union de toutes les classes de la hiérarchie polynomiale. (fr) 多項式階層（たこうしきかいそう、英: Polynomial hierarchy）は、計算量理論における計算量の階層であり、神託機械を使って P、NP、co-NP を一般化させて定義されるものである。 (ja) No ramo da Complexidade computacional a hierarquia polinomial é a hierarquia das Classes de complexidade que generaliza as classes P, NP e Co-NP para Máquinas oráculo. É uma contrapartida limitada de recursos para a Hierarquia aritmética e Hierarquia analítica da Lógica matemática. (pt) 计算复杂度理论中，多项式谱系是一个复杂度系列。它从P、NP和反NP复杂度类逐级产生至预言机。它类似于数理逻辑中算数阶层和，只不过是由逐级放宽资源限制而产生的。 (zh) В теории сложности полиномиальная иерархия — это иерархия классов сложности, которая обобщает классы P, NP, co-NP до вычислений с оракулом. (ru) У теорії складності поліноміальна ієрархія — це ієрархія класів складності, яка узагальнює класи P, NP, co-NP до обчислень з оракулом. (uk) In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH. (en) |
| rdfs:label | هرمية كثيرة الحدود (ar) Jerarquia polinòmica (ca) Polynomialzeithierarchie (de) Jerarquía polinómica (es) Hiérarchie polynomiale (fr) 多項式階層 (ja) Polynomial hierarchy (en) Hierarquia polinomial (pt) Полиномиальная иерархия (ru) Поліноміальна ієрархія (uk) 多項式譜系 (zh) |
| owl:sameAs | freebase:Polynomial hierarchy yago-res:Polynomial hierarchy wikidata:Polynomial hierarchy dbpedia-ar:Polynomial hierarchy dbpedia-ca:Polynomial hierarchy dbpedia-de:Polynomial hierarchy dbpedia-es:Polynomial hierarchy dbpedia-fr:Polynomial hierarchy dbpedia-he:Polynomial hierarchy dbpedia-ja:Polynomial hierarchy dbpedia-pt:Polynomial hierarchy dbpedia-ru:Polynomial hierarchy dbpedia-sk:Polynomial hierarchy dbpedia-uk:Polynomial hierarchy dbpedia-zh:Polynomial hierarchy https://global.dbpedia.org/id/zweg |
| prov:wasDerivedFrom | wikipedia-en:Polynomial_hierarchy?oldid=1111112196&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Polynomial_time_hierarchy.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Polynomial_hierarchy |
| is dbo:wikiPageRedirects of | dbr:Polynomial-time_hierarchy dbr:Polynomial_time_hierarchy dbr:Sigma2p dbr:NP^NP |
| is dbo:wikiPageWikiLink of | dbr:Belief_revision dbr:Quantum_complexity_theory dbr:List_of_complexity_classes dbr:List_of_computability_and_complexity_topics dbr:NP_(complexity) dbr:Richard_Lipton dbr:Richard_M._Karp dbr:Default_logic dbr:Descriptive_Complexity dbr:Descriptive_complexity_theory dbr:Indistinguishability_obfuscation dbr:Induced_matching dbr:Intersection_number_(graph_theory) dbr:Limits_of_computation dbr:List_of_mathematical_logic_topics dbr:Presburger_arithmetic dbr:♯P dbr:♯P-completeness_of_01-permanent dbr:Oracle_machine dbr:NP-easy dbr:Random_self-reducibility dbr:Seinosuke_Toda dbr:Bounded_quantifier dbr:Arithmetical_hierarchy dbr:Berman–Hartmanis_conjecture dbr:Logic_optimization dbr:Closed-world_assumption dbr:Complexity_class dbr:PH_(complexity) dbr:P_(complexity) dbr:Mahaney's_theorem dbr:Quantum_supremacy dbr:Succinct_game dbr:Maximin_share dbr:P/poly dbr:Thue_number dbr:BPP_(complexity) dbr:BQP dbr:Hedonic_game dbr:Larry_Stockmeyer dbr:Polynomial-time_reduction dbr:Albert_R._Meyer dbr:Alternating_Turing_machine dbr:PP_(complexity) dbr:Graph_isomorphism dbr:Delta dbr:Reduction_(complexity) dbr:AC0 dbr:Karp–Lipton_theorem dbr:Lance_Fortnow dbr:Hierarchy_(mathematics) dbr:Arthur–Merlin_protocol dbr:Boolean_circuit dbr:Boolean_hierarchy dbr:Boolean_satisfiability_problem dbr:Boson_sampling dbr:Pi_(disambiguation) dbr:Circuits_over_sets_of_natural_numbers dbr:Michael_Sipser dbr:Sigma_(disambiguation) dbr:Nerode_Prize dbr:Exponential_hierarchy dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_unsolved_problems_in_computer_science dbr:List_of_unsolved_problems_in_fair_division dbr:Low_(complexity) dbr:NP/poly dbr:Stable_model_semantics dbr:P_versus_NP_problem dbr:True_quantified_Boolean_formula dbr:S2P_(complexity) dbr:Sipser–Lautemann_theorem dbr:Structural_complexity_theory dbr:Polynomial-time_hierarchy dbr:Polynomial_time_hierarchy dbr:Sigma2p dbr:NP^NP |
| is foaf:primaryTopic of | wikipedia-en:Polynomial_hierarchy |
