다항식 계층 구조

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2019년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

계산 복잡성 이론에서 다항식 계층(다항식 시간 계층이라고도 함)은 NP와 co-NP 등급을 일반화하는 복잡성 계층의 계층이다.^[1]계층의 각 클래스는 PSPACE 내에 포함되어 있다.계층은 오라클 머신이나 교차 튜링 머신을 사용하여 정의할 수 있다.그것은 산술적 계층 구조와 수학 논리의 분석 계층 구조에 대한 자원 경계 대상이다.계층의 계급의 결합은 PH로 알려져 있다.

계층 내의 클래스는 정량화된 부울 공식이 유지되는지 여부를 묻는 완전한 문제(다항식 시간 감소와 관련)를 가지고 있으며, 정량화 순서에 제약이 있는 공식이다.계층에서 동일한 레벨이나 연속적인 레벨의 클래스들 사이의 평등이 그 레벨로의 계층의 "붕괴"를 의미한다고 알려져 있다.

정의들

다항식 계층의 클래스에는 여러 가지 등가 정의가 있다.

오라클 정의

다항식 계층의 오라클 정의에 대해 정의

${\displaystyle \Delta _{0}^{{0}^{P}:=\Sigma _{0}^{P}:=\Pi _{0}^{P}}={\mathsf{P}}},}$

여기서 P는 다항식 시간에 해결할 수 있는 의사결정 문제의 집합이다.그러면 i ≥ 0에 대해 정의하십시오.

${\displaystyle \Delta _{i+1}^{{p}:={\mathsf{P}^{\mathsf _{i}^{\mathsf{P}}}}}}}}}}}$

${\displaystyle \Sigma _{i+1}^{{p}:={\mathsf{NP}^{i}^{\mathsf{P}}}}}}}}}$

${\displaystyle \Pi _{i+1}^{\mathsf {P}:={\mathsf{coNP}^{\Sigma _{i}^{\mathsf{P}}}}}}}}}}}}}}$

where ${\displaystyle {\mathsf {P}}^{\rm {A}}}$ is the set of decision problems solvable in polynomial time by a Turing machine augmented by an oracle for some complete problem in class A; the classes ${\displaystyle {\mathsf {NP}}^{\rm {A}}}$ and ${\displaystyle {\mathsf {coNP}}^{\$$rm {A}}$은(는) 유사하게 정의된다$$.For example, ${\displaystyle \Sigma _{1}^{\mathsf {P}}={\mathsf {NP}},\Pi _{1}^{\mathsf {P}}={\mathsf {coNP}}}$, and ${\displaystyle \Delta _{2}^{\mathsf {P}}={\mathsf {P^{NP}}}}$ is the class of problems solvable in polynomial time with an oracle for일부 NP 완전 ^[2]문제

정량화된 부울 공식 정의

다항식 계층의 실존적/범용적 정의를 위해 L을 언어(즉, 의사결정 문제, {0,1}의 부분 집합)로 하고 ^*p를 다항식(多항식)으로 하고 정의한다.

$\displaystyle \exists ^{p}L:=\왼쪽\{x\in \{0,1\}^{0,1\}^{\lq p(x )}\right)\langle x,w\rangle \in L\right.\right\}}$

여기서 $⟨{\displaystyle }$ ${\displaystyle x}$, ${\displaystyle w}$ ${\displaystyle ⟩\in }$ { ${\displaystyle 0}$, ${\displaystyle 1{}^{\ast }}$ ∗ {\$displaystyle$ x$,w\angle \in \{0,1\}^{*}}}}}}}$는 이진 문자열 x와 w의 쌍을 하나의 이진 문자열로 표준 인코딩한 것이다$$.L represents a set of ordered pairs of strings, where the first string x is a member of ${\displaystyle \exists ^{p}L}$, and the second string w is a "short" (${\displaystyle w \leq p( x )}$) witness testifying that x is a member of ${\displaystyle \exists ^{p}L}$. In other words,${\displaystyle x}$ $\in {\displaystyle }$ ${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle p^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle x\$${\displaystyle \mathrm{in}}$ \$exists$^{$p}$${\displaystyle \mathrm{만약}}$에 and x${\displaystyle }$, ${\displaystyle w}$ ${\displaystyle ⟩}$ L ${\displaystyle \langle$ x$,w\rangle \in L}$과 같은 짧은 증인이 존재하는 경우에만. 마찬가지로 정의하십시오$.$

$\displaystyle \forall ^{p}L:=\좌측\{x\in \{0,1\}^{0,1\}^{\lq p(x )\우측)\langle x,w\rangle \in L\우측.\right\}}$

Note that De Morgan's laws hold: ${\displaystyle \left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}}$ and ${\displaystyle \left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}}$, where L^c is the complement of L.

C를 언어의 한 부류로 삼아라.이러한 연산자를 정의에 따라 전체 클래스의 언어에 대해 작업하도록 확장

${\displaystyle \exists ^{\mathsf{P}{\mathcal {C}:=\왼쪽\{\exists ^{p}L\\p{\text{}}는 다항식이고 {\mathcal}\right\}}}}}}}}}은(으)이다.$

${\displaystyle \forall ^{\mathsf{P}}{\mathcal {C}:=\left\{\forall ^{p}L\\p\text{{p}}}는 다항식이고 {\mathcal}\right\}}}}}}은(으)이다.$

Again, De Morgan's laws hold: ${\displaystyle {\mathsf {co}}\exists ^{\mathsf {P}}{\mathcal {C}}=\forall ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}}$ and ${\displaystyle {\mathsf {co}}\forall ^{\mathsf {P}}{\mathcal {C}}=\exists ^{\mathsf$${P}{\mathsf{co}}{\mathcal{C$ 여기서 $c{\displaystyle \mathsf{}}$ ${\displaystyle o\mathcal{}}$=${\displaystyle }${ ${\displaystyle L{}^{}}$ ${\displaystyle L{}^{}}$ ${\displaystyle \in }$ $}{\$$L^{c} L\in {\mathcal {C}\오른쪽$

The classes NP and co-NP can be defined as ${\displaystyle {\mathsf {NP}}=\exists ^{\mathsf {P}}{\mathsf {P}}}$, and ${\displaystyle {\mathsf {coNP}}=\forall ^{\mathsf {P}}{\mathsf {P}}}$, where P is the class of all feasibly (polynomial-time) decidable languages.다항식 계층 구조는 다음과 같이 재귀적으로 정의할 수 있다.

${\displaystyle \Sigma _{0}^{{0}^{P}:=\Pi _{0}^{0}^{P}={\mathsf {P}}}}$

${\displaystyle \Sigma _{k+1}^{\mathsf {P}:=\exists ^{\mathsf {P}\Pi _{k}^{\mathsf {P}}}}}}$

${\displaystyle \Pi \{k+1}^{\mathsf {P}:=\forall ^{\mathsf {P}\Sigma _{k}^{\mathsf {P}}}}}}$

Note that ${\displaystyle {\mathsf {NP}}=\Sigma _{1}^{\mathsf {P}}}$, and ${\displaystyle {\mathsf {coNP}}=\Pi _{1}^{\mathsf {P}}}$.

이 정의는 다항식 계층 구조와 산술적 계층 구조 사이의 밀접한 연관성을 반영하며, 여기서 R과 RE는 각각 P와 NP와 유사한 역할을 수행한다.분석 계층 구조는 또한 실제 숫자의 하위 집합의 계층 구조를 제공하는 유사한 방법으로 정의된다.

교대 튜링 머신 정의

교번 튜링 기계는 비결정론적 튜링 기계로 비최종 상태가 실존적 상태와 보편적 상태로 구분된다.그것은 만일 그것이 실존적 상태에 있고, 궁극적으로 수용하는 어떤 구성으로 전환될 수 있다, 또는 보편적 상태에 있고 모든 전환이 결국 어떤 구성을 수용하는 상태에 있다, 또는 그것이 수용적인 상태에 있다면, 결국 현재의 구성으로부터 수용하는 것이다.^[3]

${\displaystyle {우리}_{}^{}}$는 ${\displaystyle {\mathsf{}}_{}^{}}$ k P ${\$을(를) 초기 상태가 실존 상태이고 기계가 실존 상태와 보편적 상태 간에 최대 k – 1회 스왑할 수 있는 모든 경로가 되도록 다항 시간 내에 교대 튜링 시스템에 의해 수용되는 언어의 등급으로$$ 정의한다.초기 상태가 범용 상태라는 점을 제외하고 ${\displaystyle {\pi k}_{}^{}}$ ${\displaystyle {\mathsf{}}_{}^{}}$ ${\$을(를) 유사하게 정의한다.^[4]

만일 우리가 실존 상태와 보편적 상태 사이의 최대 k – 1 스왑의 요건을 생략하여 우리의 교대 튜링 기계가 다항 시간 내에 작동하도록 요구한다면, 우리는 PSPACE와 동등한 등급 AP의 정의를 얻게 된다.^[5]

다항식 계층 구조에서 클래스 간 관계

다항식 계층 구조에서 모든 계층의 결합은 복잡도 클래스 PH이다.

이 정의는 다음과 같은 관계를 의미한다.

${\displaystyle \Sigma _{i}^{\mathsf{P}}\subseteq \Delta _{i+1}^{p}\mathsf {P}}}$

${\displaystyle \Pi \i}^{{i}^{{p}}\subseteq \Delta _{i+1}^{p}\subseteq \Pi _{i+1}^{mathsf {P}}}}}}$

${\displaystyle \Sigma _{i}^{{i}^{\mathsf{P}={\mathsf{co}}\Pi _{i}^{\mathsf{P}}}}}}$

포함이 적절하다고 알려진 산술적, 분석적 계층 구조와 달리, 이러한 포함 중 하나라도 모두 적절하다고 널리 믿어지고 있지만, 과연 적절한가 하는 것은 공공연한 의문이다.만약 어떤 Σ kP= Σ k+1P{\displaystyle \Sigma_{k}^{\mathsf{P}}=\Sigma _{k+1}^{\mathsf{P}}}, 또는 어떤 Σ k.P는 Π k P{\displaystyle \Sigma_{k}^{\mathsf{P}}=\Pi _{k}^{\mathsf{P}}}, 다음 계층이 붕괴되면 k단계:모두에게 나는입니다.;k{\displaystyle i>, k}, Σ 나는 P)Σ는 k p${\displaystyle \Sigma _{i}^{\mathsf{P}=\Sigma _{k}^{$k}^{\$mathsf{P$^[6] 특히 해결되지 않은 문제와 관련하여 다음과 같은 함의가 있다.

• P = NP인 경우 및 PH인 경우에만 해당된다.^[7]
• NP = co-NP인 경우 NP = PH. (co-NP는 $\pi {\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {\mathsf{}}_{}^{}}$ P$${\$displaystyle \Pi _{1}^{\mathsf{P}}.)$

NP = PH가 2단계로 붕괴된 경우라고도 한다.사례 P = NP는 PH 대 P의 붕괴에 해당한다.

1단계까지 무너지는 문제는 일반적으로 극히 어려운 것으로 생각된다.대부분의 연구자들은 심지어 2단계까지 붕괴를 믿지 않는다.

다른 클래스와의 관계

다항식 계층 구조는 지수 계층 구조와 산술 계층 구조의 아날로그(더 낮은 복잡도)이다.

PSpace 내에 PH가 포함되어 있는 것으로 알려져 있으나, 두 등급이 동일한지는 알려져 있지 않다.이 문제에 대한 한 가지 유용한 개혁은 유한 구조물에 대한 2차 논리가 타동성 폐쇄 사업자의 추가로부터 추가 전력을 얻지 못하는 경우에만 PH = PSPACE이다.

만약 다항식 계층 구조가 완전한 문제를 가지고 있다면, 그것은 단지 많은 뚜렷한 수준만을 가지고 있을 뿐이다.PSPACE-완전 문제가 있으므로 PSPACE = PH이면 다항식 ${\displaystyle {}_{}^{}}$이 붕괴되어야 하며, PSPACE-완전 문제는 ${\displaystyle {bek}_{}^{}}$ k P ${\$일부$$ k에 대해 완료 문제가 발생하므로, 우리는 알고 있다.^[8]

다항식 계층 구조의 각 클래스는 $\le {\displaystyle {}_{m\mathrm{}}^{}}$ ${\displaystyle P_{\mathsf{}}^{}}$ ${\$ -완료$$ 문제(다항식 시간 다항식 다항식 감소 하에서 완료되는 문제)를 포함한다.Furthermore, each class in the polynomial hierarchy is closed under ${\displaystyle \leq _{\rm {m}}^{\mathsf {P}}}$-reductions: meaning that for a class C in the hierarchy and a language ${\displaystyle L\in {\mathcal {C}}}$, if ${\displaystyle A\leq _{\rm {m}}^{\mathsf {P}}L}$, then${\displaystyle A}$ ${\displaystyle \in }$ ${\displaystyle C\mathcal{}}$ ${\$도.These two facts together imply that if ${\displaystyle K_{i}}$ is a complete problem for ${\displaystyle \Sigma _{i}^{\mathsf {P}}}$, then ${\displaystyle \Sigma _{i+1}^{\mathsf {P}}={\mathsf {NP}}^{K_{i}}}$, and ${\disp$$laystyle \Pi _{i+1}^{\mathsf {P}}={\mathsf {coNP}}^{K_{i}}}$. For instance, ${\displaystyle \Sigma _{2}^{\mathsf {P}}={\mathsf {NP}}^{\mathsf {SAT}}}$. In other words, if a language is defined based on some oracle in C, then we can assume that it is defined based on a complete problem for C.그러므로 완전한 문제는 그들이 완성한 클래스의 "대표자"로 작용한다.

Sipser-Lautemann 정리는 클래스 BPP가 다항식 계층의 두 번째 레벨에 포함되어 있다고 명시한다.

칸난의 정리에는 어떤 $k$에 대해서도 for ${\displaystyle {2\mathrm{}}_{}}$ ${\$}가 SIZE(n^k)에 포함되어 있지$$ 않다고 되어 있다.

토다의 정리에는 다항식 계급이 P에^#P 포함되어 있다고 되어 있다.

문제

참고 항목

• 엑스트라타임
• 지수 계층 구조
• 산술 계층 구조

참조

일반참조

1. Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"
2. A. R. 마이어와 L. J. 스톡마이어.제곱을 갖는 정규식의 동등성 문제에는 지수적 공간이 필요하다.제13회 IEEE 전환 및 자동화가론 심포지엄의 진행, 페이지 125–129, 1972.다항식 서열을 도입한 논문.
3. L. J. 스톡마이어.다항식 시간 계층.이론 컴퓨터 과학, vol.3, 페이지 1–22, 1976.
4. C. 파파디미트리오.계산 복잡성.애디슨 웨슬리, 1994년17장다항식 계층 구조, 페이지 409-438.
5. Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. 제7.2절: 다항식 계층 구조, 페이지 161–167.

인용구