About: Polynomial hierarchy

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Polynomial hierarchy Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Group100031264, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FPolynomial_hierarchy

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.

Attributes	Values
rdf:type	software yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264
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)
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)
foaf:depiction
dcterms:subject	Hierarchy Structural complexity theory
Wikipage page ID	658651 (xsd:integer)
Wikipage revision ID	1111112196 (xsd:integer)
Link from a Wikipage to another Wikipage	NP (complexity) Bounded-error probabilistic polynomial David S. Johnson De Morgan's laws Decision problem PSPACE-complete Analytical hierarchy Hierarchy Mathematical logic Oracle machine Christos Papadimitriou Co-NP Symposium on Switching and Automata Theory Arithmetical hierarchy Structural complexity theory Complexity class Computational complexity theory PH (complexity) P (complexity) Transitive closure Circuit minimization Larry Stockmeyer Polynomial-time reduction Recursively enumerable language Albert R. Meyer EXPTIME Alternating Turing machine PSPACE Formal language Toda's theorem Karp–Lipton theorem Hierarchy (mathematics) Boolean function Boolean satisfiability problem Polynomial Polynomial time Turing machine SO (complexity) Exponential hierarchy Computers and Intractability: A Guide to the Theory of NP-Completeness P versus NP problem Sipser–Lautemann theorem Analytic hierarchy Arithmetic hierarchy Quantified Boolean formula Michael R. Garey Decidable language Complete problem TQBF dbr:Doi:10.1016/0304-3975(76)90061-X
Link from a Wikipage to an external page	http://www.cs.princeton.edu/theory/complexity/ http://ovid.cs.depaul.edu/documents/phcom.pdf
sameAs	Polynomial hierarchy Polynomial hierarchy Polynomial hierarchy Polynomial hierarchy Polynomial hierarchy Polynomial hierarchy Polynomial hierarchy Polynomial hierarchy Polynomial hierarchy Polynomial hierarchy Polynomial hierarchy Polynomial hierarchy Polynomial hierarchy Polynomial hierarchy

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software