P(복잡성)

계산 복잡성 이론에서 PTIME 또는 DTIME(n^O(1))라고도 하는 P는 근본적인 복잡성 등급이다. 다항식 계산 시간 또는 다항식 시간을 사용하여 결정론적 튜링 기계로 해결할 수 있는 모든 의사결정 문제를 담고 있다.

코브햄의 논문은 P가 "효율적으로 해결할 수 있다"거나 "추상할 수 있다"는 계산 문제의 등급이라고 주장한다. 이것은 부정확하다: 실제로 P에 있다고 알려져 있지 않은 몇몇 문제들은 실제적인 해결책을 가지고 있고, P에 있는 몇몇 문제들은 그렇지 않지만, 이것은 유용한 경험의 법칙이다.

정의

L 언어는 다음과 같은 결정론적 튜링 기계 M이 존재하는 경우에만 P에 있다.

모든 입력에서 다항식 시간에 대한 M 런
모든 x의 경우 L, M 출력 1
L이 아닌 모든 x에 대해, M 출력 0

P는 부울 회로의 균일한 계열로도 볼 수 있다. 다항식 부울 회로의 균일 계열의 다항식 시간 부울 회로가 존재하는 경우에만 언어 L이 P에 표시되며 $\{C_{n}:n\in \mathbb {N} \}$ 이러한 경우 ${$ n $\{C_{n}:n\in \mathbb {N} \}$ ${\displaystyle$ \{ $C_{n}:n\in \mathb {N}$ $\{C_{n}:n\in \mathbb {N} \}$

모든 $n\in \mathbb {N}$ $n\in \mathbb {N}$ $n\in \mathbb {N}$ ${\$ $C_{n}$ $C_{n}$ ${\$ 에 대해 n비트를 입력으로 사용하고 $C_{n}$ 1비트를 출력한다.
L의 모든 x에 대해, C $C_{|x|}(x)=1$ ( x $C_{|x|}(x)=1$ ) $C_{|x|}(x)=1$ = $C_{|x|}(x)=1$ ${\displaystyle C_{$ x $}(x)=1$ }
L에 없는 모든 x에 대해, C $C_{|x|}(x)=0$ ( $C_{|x|}(x)=0$ ) $C_{|x|}(x)=0$ = $C_{|x|}(x)=0$ ${\displaystyle C_{$ x $}(x)=0}$

회로 정의는 복잡도 등급을 변경하지 않고 로그 공간 균일 패밀리만 사용하도록 약화될 수 있다.

P의 주목할 만한 문제점

P는 선형 프로그래밍의 결정판, 최대 일치점 찾기 등 많은 자연적인 문제를 포함하고 있는 것으로 알려져 있다. 2002년에는 숫자가 프라임인지를 판단하는 문제가 P에 있다는 것을 보여주었다.^[1] 기능 문제의 관련 등급은 FP이다.

P에 대해서는 교번 그래프의 st-연결성(또는 도달성)을 포함하여 몇 가지 자연 문제가 완전하다.^[2] P-완전 문제에 관한 기사는 P에 관련된 문제를 추가로 열거하고 있다.

다른 클래스와의 관계

P의 일반화는 NP로, 다항식 시간에 실행되는 비결정론적 튜링 기계에 의해 해독될 수 있는 의사결정 문제의 등급이다. 마찬가지로, 각 "예" 인스턴스마다 다항식 크기 인증서가 있고 다항식 시간 결정론적 튜링 기계로 인증서를 확인할 수 있는 의사결정 문제의 등급이다. The class of problems for which this is true for the "no" instances is called co-NP. P is trivially a subset of NP and of co-NP; most experts believe it is a proper subset,^[3] although this (the ${\mathsf {P}}\subsetneq {\mathsf {NP}}$ hypothesis) remains unproven. 또 다른 개방적인 문제는 NP = co-NP인지 여부인데,^[4] P = co-P이기 때문에 부정적인 대답은 ${\mathsf {P}}\subsetneq {\mathsf {NP}}$ ${\mathsf {P}}\subsetneq {\mathsf {NP}}$ ${\mathsf {P}}\subsetneq {\mathsf {NP}}$ ${\mathsf {P}}\subsetneq {\mathsf {NP}}$ ${\$ 을(를) 암시할 수 있다 ${\mathsf {P}}\subsetneq {\mathsf {NP}}$

또한 P는 최소한 L만큼 큰 것으로 알려져 있는데, 이는 로그의 메모리 공간에서 해독할 수 없는 문제의 등급이다. $O(\log n)$ $O(\log n)$ ) ${\displaystyle$ O $(\log$ n $)}$ 공간을 $O(\log n)$ 사용하는 데시더는 $2^{O(\log n)}=n^{O(1)}$ (log $2^{O(\log n)}=n^{O(1)}$ $2^{O(\log n)}=n^{O(1)}$ ) $2^{O(\log n)}=n^{O(1)}$ = 1 $2^{O(\log n)}=n^{O(1)}$ {\ $displaystyle 2^{O(\log$ n $)}=n^{O($ 1)를 $2^{O(\log n)}=n^{O(1)}$ 초과할 수 없으므로 L은 P의 하위 집합이다. 또 다른 중요한 문제는 L = P. 우리는 Turing 기계를 교대로 사용함으로써 로그 메모리에서 해결할 수 있는 문제들의 집합인 P = AL을 알고 있다. P는 또한 다항식 공간에서 결정 불가능한 문제의 등급인 PSPACE보다 크지 않은 것으로 알려져 있다. 다시 말하지만, P = PSPACE가 개방적인 문제인지 아닌지가 문제다. 요약하면:

{\mathsf {L}\subseteq {\mathsf {AL}={\mathsf {NP}\subseteq {\mathsf {PSPACE}\subseteq {\mathsf {EXPTIME}}}}}

여기서 EXPTIME은 지수 시간 내에 해결할 수 있는 문제의 등급이다. 위에 표시된 모든 클래스 중 두 가지 엄격한 제한 사항만 알려져 있다.

P는 EXPTIME에 엄격히 포함되어 있다. 따라서 모든 EXPTIME-hard 문제는 P 밖에 있으며, 위의 P 오른쪽에 있는 것 중 적어도 하나는 엄격하다(사실, 세 가지 모두 엄격하다는 것이 널리 알려져 있다.
L은 PSpace에 엄격히 포함되어 있다.

P에서 가장 어려운 문제는 P-완전성이다.

P의 또 다른 일반화는 P/poly 또는 Nonuniform Polymal-Time이다. 만약 문제가 P/poly에 있다면, 입력의 길이에만 의존하는 조언 문자열이 주어진다면, 그것은 결정론적 다항식 시간에 해결될 수 있다. 그러나 NP의 경우와 달리, 다항 시간 기계는 사기성 조언 문자열을 감지할 필요가 없으며 검증자가 아니다. P/폴리(P/poly)는 BPP를 포함한 거의 모든 실제적인 문제를 포함하고 있는 큰 수업이다. NP를 포함하면 다항식 계층이 두 번째 수준으로 축소된다. 반면에, 그것은 또한 어떤 미해결 문제의 단일 버전과 같은 일부 미해결 문제를 포함한 일부 비실용적인 문제들을 포함하고 있다.

1999년에는 진이 카이, D. 오기하라 미쓰노리가 작업으로 짓고 있는 시바쿠마르는 P-완전인 희박한 언어가 존재한다면 L = P라는 것을 보여주었다.^[5]

특성.

다항식 시간 알고리즘은 구성 하에서 폐쇄된다. 직관적으로 이것은 함수 호출이 일정한 시간이라고 가정하는 다항 시간 함수를 쓰고, 함수라고 불리는 것 자체가 다항 시간을 필요로 한다면 전체 알고리즘이 다항 시간을 소모한다고 말한다. 이것의 한 가지 결과는 P가 스스로 낮다는 것이다. 이것은 또한 P가 기계에 독립적인 등급으로 간주되는 주요 이유 중 하나이다. 다항식 시간에 시뮬레이션될 수 있는 임의의 기계 "기능"은 주 다항식 시간 알고리즘으로 간단하게 구성하여 보다 기본적인 기계의 다항식 시간 알고리즘으로 줄일 수 있다.

P의 언어도 반전, 교차, 결합, 결합, 클레인 폐쇄, 역동형성, 보완성 속에서 폐쇄된다.^[6]

다항식 시간 알고리즘의 순수 존재 증명

일부 문제는 다항식 시간에 해결할 수 있는 것으로 알려져 있지만 이를 해결하기 위한 구체적인 알고리즘은 알려져 있지 않다. 예를 들어, 로버트슨-이전-시모어 정리에서는 토러스(torus)에 내장할 수 있는 그래프 집합을 특징짓는(예를 들어) 금지된 미성년자의 유한한 목록이 있음을 보장하고, 더욱이 로버슨과 시모어는 그래프가 주어진 그래프를 마이너로서 가지고 있는지를 판단하는 O(n³) 알고리즘이 있음을 보여주었다. 이는 특정 그래프를 토러스(torus)에 삽입할 수 있는지 여부를 결정하기 위한 다항 시간 알고리즘이 있다는 비건설적 증거를 산출한다.

대체 특성화

서술적 복잡도에서 P는 명령된 구조물에 최소 고정점 운영자가 추가된 1차 논리인 FO(LFP)에서 표현할 수 있는 문제로 설명할 수 있다. 1999년 이머만의 서술적 복잡성에 관한 교과서에서 이머만은 이 결과를 바르디와^[8] 이머만에게 돌렸다.^[7]^[9]

PTIME은 (긍정적인) 범위 연결 그래머에 해당한다고 2001년에 발표되었다.^[10]

역사

코젠은^[11] 코브햄과 에드몬드가 "일반적으로 다항식 시간의 개념의 발명을 인정받았다"고 말한다. 코브햄은 효율적인 알고리즘을 특징짓는 강력한 방법으로 클래스를 발명하여 코브햄의 논문을 이끌어냈다. 하지만 H.C.Pocklington, 1910년 paper,[12][13]에 2차 congruences를 해결하기 위하며, 그리고 비례"그 탄성 계수 자체 또는 그 제곱 근"시간이 걸렸다 사람이 이 분열과 비교했다 시간"탄성 계수의 로그의에 비례", 따라서 명시적으로 a의 구분을 그리는 것을 관찰했다 두 알고리즘 분석했다nalgo다항식 시간에 실행된 Rithm과 그렇지 않은 Rithm.

메모들

^ 마닌드라 아그라왈, 네에라즈 카얄, 니틴 색세나, "PRIMES는 P에 있다", 수학 연보 160(2004), 제 2, 페이지 781–793.
^ Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. ISBN 978-0-387-98600-5.
^ Johnsonbaugh, Richard; Schaefer, Marcus, Algorithm, 2004 Pearson Education, 458페이지, ISBN 0-02-360692-4
^ "complexity theory - Why is co-P = P". Stack Overflow. Archived from the original on 14 October 2020. Retrieved 2020-10-14.
^ 진이 카이, D. 시바쿠마르. P를 위한 희박한 하드 세트: 하트마니스의 추측에 대한 해결. 컴퓨터 및 시스템 과학 저널, 제58권, 발행물 2, 페이지 2.280–296. 1999. ISSN 0022-0000. 앳 시티서
^ Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). Introduction to automata theory, languages, and computation (2. ed.). Boston: Addison-Wesley. pp. 425–426. ISBN 978-0201441246.
^ Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. p. 66. ISBN 978-0-387-98600-5.
^ Vardi, Moshe Y. (1982). "The Complexity of Relational Query Languages". STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 137–146. doi:10.1145/800070.802186.
^ Immerman, Neil (1982). "Relational Queries Computable in Polynomial Time". STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 147–152. doi:10.1145/800070.802187. Information and Control의 개정판, 68 (1986), 86–104.
^ Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. pp. 5 and 37. ISBN 978-3-642-14846-0. 증거자료로 http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf을 인용하다.
^ Kozen, Dexter C. (2006). Theory of Computation. Springer. p. 4. ISBN 978-1-84628-297-3.
^ Pocklington, H. C. (1910–1912). "The determination of the exponent to which a number belongs, the practical solution of certain congruences, and the law of quadratic reciprocity". Proc. Camb. Phil. Soc. 16: 1–5.
^ Gautschi, Walter (1994). Mathematics of computation, 1943–1993: a half-century of computational mathematics: Mathematics of Computation 50th Anniversary Symposium, August 9–13, 1993, Vancouver, British Columbia. Providence, RI: American Mathematical Society. pp. 503–504. ISBN 978-0-8218-0291-5.

참조

Cobham, Alan (1965). "The intrinsic computational difficulty of functions". Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein. 알고리즘 소개, Second Edition. MIT 프레스와 맥그로-힐, 2001. ISBN 0-262-03293-7 제34.1절: 다항 시간, 페이지 971–979.
Papadimitriou, Christos H. (1994). Computational complexity. Reading, Mass.: Addison–Wesley. ISBN 978-0-201-53082-7.
Sipser, Michael (2006). Introduction to the Theory of Computation, 2nd Edition. Course Technology Inc. ISBN 978-0-534-95097-2. 제7.2절: 등급 P, 페이지 256–263;

외부 링크

복잡성 동물원: 클래스 P
복잡성 동물원: 클래스 P/폴리

[1] 마닌드라 아그라왈, 네에라즈 카얄, 니틴 색세나, "PRIMES는 P에 있다", 수학 연보 160(2004), 제 2, 페이지 781–793.

[Immerman_Reachability-2] Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. ISBN 978-0-387-98600-5.

[3] Johnsonbaugh, Richard; Schaefer, Marcus, Algorithm, 2004 Pearson Education, 458페이지, ISBN 0-02-360692-4

[4] "complexity theory - Why is co-P = P". Stack Overflow. Archived from the original on 14 October 2020. Retrieved 2020-10-14.

[5] 진이 카이, D. 시바쿠마르. P를 위한 희박한 하드 세트: 하트마니스의 추측에 대한 해결. 컴퓨터 및 시스템 과학 저널, 제58권, 발행물 2, 페이지 2.280–296. 1999. ISSN 0022-0000. 앳 시티서

[6] Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). Introduction to automata theory, languages, and computation (2. ed.). Boston: Addison-Wesley. pp. 425–426. ISBN 978-0201441246.

[7] Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. p. 66. ISBN 978-0-387-98600-5.

[8] Vardi, Moshe Y. (1982). "The Complexity of Relational Query Languages". STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 137–146. doi:10.1145/800070.802186.

[9] Immerman, Neil (1982). "Relational Queries Computable in Polynomial Time". STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing. pp. 147–152. doi:10.1145/800070.802187. Information and Control의 개정판, 68 (1986), 86–104.

[Kallmeyer2010-10] Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. pp. 5 and 37. ISBN 978-3-642-14846-0. 증거자료로 http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf을 인용하다.

[11] Kozen, Dexter C. (2006). Theory of Computation. Springer. p. 4. ISBN 978-1-84628-297-3.

[12] Pocklington, H. C. (1910–1912). "The determination of the exponent to which a number belongs, the practical solution of certain congruences, and the law of quadratic reciprocity". Proc. Camb. Phil. Soc. 16: 1–5.

[13] Gautschi, Walter (1994). Mathematics of computation, 1943–1993: a half-century of computational mathematics: Mathematics of Computation 50th Anniversary Symposium, August 9–13, 1993, Vancouver, British Columbia. Providence, RI: American Mathematical Society. pp. 503–504. ISBN 978-0-8218-0291-5.

[1]

[2]

[3]

[4]

[5]

[6]

[8]

[7]

[9]

[10]

[11]

v t 중요 복잡성 클래스(추가)
실현 가능한 것으로 간주됨	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-완전 ZPP RP BPP BQP APX
실행 불가능한 것으로 의심됨	UP NP NP-완전 NP-하드 공동 NP 공동 NP-완전 AM QMA PH ⊕P PP #P #P-완전 IP 프스페이스 PSpace-완전
실현 불가능한 것으로 간주됨	엑스트라타임 NEXPTIME 엑스포스페이스 2-EXPTIME 초등 PR R RE 모두
클래스 계층	다항식 계층 구조 지수 계층 구조 그르제고르차이크 계층 구조 산술 계층 구조 부울 계층 구조
계급가족	디타임 NTIME 디스페이스 NSpace 확률적으로 확인할 수 있는 증거 인터랙티브 프루프 시스템

Search