| dbo:abstract
|
- En teoria de la complexitat, la classe de complexitat PH és la unió de totes les classes de complexitat dins la jerarquia polinòmica: va ser el primer en definir aquesta classe. És un cas especial de . També es pot definir com el conjunt de llenguatges expressats per lògica de segon ordre. (ca)
- في نظرية التعقيد الحسابي الصنف PH هو توحيد كل الاقسام في هرمية كثيرة الحدود. لقد تم تعريف هذا القسم لأول مرة بواسطة لاري ستوكماير. وهذا القسم يتبع P#P = P وكذلك يتبع بيسبايس. PH يحتوي معظم الاقسام في بيسبايس مثل: NP ,P,كو-إن بي كما أنه يحوي اقسام تعقيد احتمالية مثل: BPP , RP , ولكن هناك دلائل على أنَّ لا يتبع PH . P=NP إذا وفقط إذا PH=P لذا فانه كفاية أن يُبرهن أنَّ P≠PH لكي نبرهن أن P≠NP . (ar)
- En théorie de la complexité, PH est l'union des classes de complexité de la hiérarchie polynomiale : PH a été introduite par Larry J. Stockmeyer en 1977. (fr)
- En teoría de la complejidad computacional, la clase de complejidad PH es la unión de todas las clases de complejidad de la jerarquía polinómica. (Tiempo y espacio) PH está contenida en las clases PSPACE y PPP que es la clase de los problemas de decisión que pueden ser resueltos en tiempo polinómico en una máquina de Turing con acceso a un oráculo PP.
* Datos: Q1063380 (es)
- In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH was first defined by Larry Stockmeyer. It is a special case of hierarchy of bounded alternating Turing machine. It is contained in P#P = PPP (by Toda's theorem; the class of problems that are decidable by a polynomial time Turing machine with access to a #P or equivalently PP oracle), and also in PSPACE. PH has a simple logical characterization: it is the set of languages expressible by second-order logic. PH contains almost all well-known complexity classes inside PSPACE; in particular, it contains P, NP, and co-NP. It even contains probabilistic classes such as BPP and RP. However, there is some evidence that BQP, the class of problems solvable in polynomial time by a quantum computer, is not contained in PH. P = NP if and only if P = PH. This may simplify a potential proof of P ≠ NP, since it is only necessary to separate P from the more general class PH. (en)
- 계산 복잡도 이론에서 복잡도 종류 PH는 에 있는 모든 복잡도 종류의 합집합이다. PH는 래리 스톡마이어(Larry Stockmeyer)가 처음 정의하였다. 이 복잡도 종류는 신탁 기계에 접근하는 다항 시간 튜링 기계를 써서 판정할 수 있는 문제인 PPP에 속한다. 에 따르면 P#P에 속하기도 한다. 그리고 PSPACE에도 속한다. PH는 로 표현할 수 있는 언어의 집합이라는 간단한 논리적 특징이 있다. PH는 PSPACE에 속하는 것 중에서 잘 알려진 복잡도 종류를 거의 모두 포함한다. 여기에는 P, NP, co-NP 따위도 들어가고, 확률적 복잡도 종류인 BPP나 RP도 들어간다. 이것은 P ≠ NP라면 그 증명을 쉽게 하는 데 쓸 수 있다. P를 더 일반적인 종류인 PH에서 분리하기만 하면 되기 때문이다. (ko)
- 計算複雑性理論における複雑性クラス PH とは、多項式階層にある全ての複雑性クラスの和集合である。次のように表される。 PH は Larry Stockmeyer が最初に定義した。これを包含するクラスとして、PPP（PPをオラクルとして持つ神託機械で多項式時間で解ける問題のクラス）、P#P（戸田の定理による）、PSPACE がある。 PH の論理的な特徴付けはごく単純。つまり、二階述語論理で可能な全ての言明の集合である。 PH は PSPACE に含まれる既知の複雑性クラスのほとんどを包含している。特に P、NP、co-NP が含まれる。また、確率的なクラスである BPP や RP も包含している。 P = NP の必要十分条件は P = PH であることである。つまり、より一般的なクラス PH から P を分離できさえすればよいので、P ≠ NP の証明の単純化に繋がるかも知れない（P≠NP予想）。 (ja)
- Na teoria da complexidade computacional, a classe de complexidade de PH é a união de todas as classes de complexidade na hierarquia polinomial: O PH foi primeiramente definido por Larry Stockmeyer. é um caso especial de hierarquia de limitado alternando máquina de Turing. Ele está contido em P#P = PPP (por Toda teorema; a classe de problemas que são decidível por um tempo polinomial máquina de Turing com acesso a um #P ou equivalentemente PP oracle), e também em PSPACE. O PH tem uma simples lógica de caracterização: é o conjunto de idiomas que podem ser expressadas através de segunda ordem lógica. PH contém quase todas as classes conhecidas de complexidade dentro de PSPACE; em particular, contém P, NPe co-NP. Ele ainda contém classes probabilística como BPP e RP. No entanto, há algumas evidências de que BQP, a classe de problemas resolvidos em tempo polinomial por um computador quântico, não está contido no PH. P = NP se e somente se P = PH. Isso pode simplificar a um potencial de prova de P ≠ NP, pois só é necessário separar a P a partir do mais geral da classe de PH. (pt)
- Клас складності PH (від англ. polynomial hierarchy) — об'єднання всіх класів складності з поліноміальної ієрархії: Таким чином, предикат належить до класу PH, якщо існує таке k, що предикат належить до класу або . Також кажуть, що мова, розпізнавана таким предикатом (тобто множина всіх слів, на яких предикат повертає 1), належить до класу PH. Клас PH вперше визначив . (uk)
- Класс сложности PH (от англ. polynomial hierarchy) — объединение всех классов сложности из полиномиальной иерархии: Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит классу или . Также говорят, что язык, распознаваемый таким предикатом (то есть множество всех слов, на которых предикат возвращает 1), принадлежит классу PH. (ru)
- 在計算複雜度理論內，複雜度類PH代表所有在多項式譜系裡面的複雜度類聯集，亦即： PH最早是由定義，是一個受限交替式圖靈機(bounded alternating Turing machine)其譜系(hierarchy)的特例。這個複雜度包含於PPP(包含問題可以由多項式時間圖靈機，並且能取用PP 神諭的機器所解決的複雜度類。), P#P (根據),以及PSPACE裡面。 PH有一個簡單的邏輯描述方法：PH是一個能以二階邏輯所表示語言的集合。 PH包含了幾乎所有在PSPACE裡面有名的複雜度類;舉例來說，像是P, NP，和co-NP。甚至還包含了一些概率複雜度類像是BPP和RP。然而，有一些證據指出BQP(以量子電腦可以在多項式時間之內解決的問題)並不包含在PH裡面(Aaronson 2010). P = NP若且唯若P = PH。這可能是一個比較簡單證明P ≠ NP的方式，因為我們只要把P從比較廣義的 PH分別出來即可。 (zh)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3232 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En teoria de la complexitat, la classe de complexitat PH és la unió de totes les classes de complexitat dins la jerarquia polinòmica: va ser el primer en definir aquesta classe. És un cas especial de . També es pot definir com el conjunt de llenguatges expressats per lògica de segon ordre. (ca)
- في نظرية التعقيد الحسابي الصنف PH هو توحيد كل الاقسام في هرمية كثيرة الحدود. لقد تم تعريف هذا القسم لأول مرة بواسطة لاري ستوكماير. وهذا القسم يتبع P#P = P وكذلك يتبع بيسبايس. PH يحتوي معظم الاقسام في بيسبايس مثل: NP ,P,كو-إن بي كما أنه يحوي اقسام تعقيد احتمالية مثل: BPP , RP , ولكن هناك دلائل على أنَّ لا يتبع PH . P=NP إذا وفقط إذا PH=P لذا فانه كفاية أن يُبرهن أنَّ P≠PH لكي نبرهن أن P≠NP . (ar)
- En théorie de la complexité, PH est l'union des classes de complexité de la hiérarchie polynomiale : PH a été introduite par Larry J. Stockmeyer en 1977. (fr)
- En teoría de la complejidad computacional, la clase de complejidad PH es la unión de todas las clases de complejidad de la jerarquía polinómica. (Tiempo y espacio) PH está contenida en las clases PSPACE y PPP que es la clase de los problemas de decisión que pueden ser resueltos en tiempo polinómico en una máquina de Turing con acceso a un oráculo PP.
* Datos: Q1063380 (es)
- 계산 복잡도 이론에서 복잡도 종류 PH는 에 있는 모든 복잡도 종류의 합집합이다. PH는 래리 스톡마이어(Larry Stockmeyer)가 처음 정의하였다. 이 복잡도 종류는 신탁 기계에 접근하는 다항 시간 튜링 기계를 써서 판정할 수 있는 문제인 PPP에 속한다. 에 따르면 P#P에 속하기도 한다. 그리고 PSPACE에도 속한다. PH는 로 표현할 수 있는 언어의 집합이라는 간단한 논리적 특징이 있다. PH는 PSPACE에 속하는 것 중에서 잘 알려진 복잡도 종류를 거의 모두 포함한다. 여기에는 P, NP, co-NP 따위도 들어가고, 확률적 복잡도 종류인 BPP나 RP도 들어간다. 이것은 P ≠ NP라면 그 증명을 쉽게 하는 데 쓸 수 있다. P를 더 일반적인 종류인 PH에서 분리하기만 하면 되기 때문이다. (ko)
- 計算複雑性理論における複雑性クラス PH とは、多項式階層にある全ての複雑性クラスの和集合である。次のように表される。 PH は Larry Stockmeyer が最初に定義した。これを包含するクラスとして、PPP（PPをオラクルとして持つ神託機械で多項式時間で解ける問題のクラス）、P#P（戸田の定理による）、PSPACE がある。 PH の論理的な特徴付けはごく単純。つまり、二階述語論理で可能な全ての言明の集合である。 PH は PSPACE に含まれる既知の複雑性クラスのほとんどを包含している。特に P、NP、co-NP が含まれる。また、確率的なクラスである BPP や RP も包含している。 P = NP の必要十分条件は P = PH であることである。つまり、より一般的なクラス PH から P を分離できさえすればよいので、P ≠ NP の証明の単純化に繋がるかも知れない（P≠NP予想）。 (ja)
- Клас складності PH (від англ. polynomial hierarchy) — об'єднання всіх класів складності з поліноміальної ієрархії: Таким чином, предикат належить до класу PH, якщо існує таке k, що предикат належить до класу або . Також кажуть, що мова, розпізнавана таким предикатом (тобто множина всіх слів, на яких предикат повертає 1), належить до класу PH. Клас PH вперше визначив . (uk)
- Класс сложности PH (от англ. polynomial hierarchy) — объединение всех классов сложности из полиномиальной иерархии: Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит классу или . Также говорят, что язык, распознаваемый таким предикатом (то есть множество всех слов, на которых предикат возвращает 1), принадлежит классу PH. (ru)
- 在計算複雜度理論內，複雜度類PH代表所有在多項式譜系裡面的複雜度類聯集，亦即： PH最早是由定義，是一個受限交替式圖靈機(bounded alternating Turing machine)其譜系(hierarchy)的特例。這個複雜度包含於PPP(包含問題可以由多項式時間圖靈機，並且能取用PP 神諭的機器所解決的複雜度類。), P#P (根據),以及PSPACE裡面。 PH有一個簡單的邏輯描述方法：PH是一個能以二階邏輯所表示語言的集合。 PH包含了幾乎所有在PSPACE裡面有名的複雜度類;舉例來說，像是P, NP，和co-NP。甚至還包含了一些概率複雜度類像是BPP和RP。然而，有一些證據指出BQP(以量子電腦可以在多項式時間之內解決的問題)並不包含在PH裡面(Aaronson 2010). P = NP若且唯若P = PH。這可能是一個比較簡單證明P ≠ NP的方式，因為我們只要把P從比較廣義的 PH分別出來即可。 (zh)
- In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH was first defined by Larry Stockmeyer. It is a special case of hierarchy of bounded alternating Turing machine. It is contained in P#P = PPP (by Toda's theorem; the class of problems that are decidable by a polynomial time Turing machine with access to a #P or equivalently PP oracle), and also in PSPACE. PH has a simple logical characterization: it is the set of languages expressible by second-order logic. (en)
- Na teoria da complexidade computacional, a classe de complexidade de PH é a união de todas as classes de complexidade na hierarquia polinomial: O PH foi primeiramente definido por Larry Stockmeyer. é um caso especial de hierarquia de limitado alternando máquina de Turing. Ele está contido em P#P = PPP (por Toda teorema; a classe de problemas que são decidível por um tempo polinomial máquina de Turing com acesso a um #P ou equivalentemente PP oracle), e também em PSPACE. (pt)
|
| rdfs:label
|
- PH(التعقيد الحسابي) (ar)
- PH (Complexitat) (ca)
- PH (clase de complejidad) (es)
- PH (complexité) (fr)
- PH (計算複雑性理論) (ja)
- PH (복잡도) (ko)
- PH (complexity) (en)
- PH (complexidade) (pt)
- Класс PH (ru)
- Клас складності PH (uk)
- PH (複雜度) (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
