P (복잡도)

위키백과 ― 우리 모두의 백과사전.

계산 복잡도 이론에서, P는 결정론적 튜링 기계로 다항시간에 풀 수 있는 판정문제들로 구성된 복잡도 종류이다.

P에는 많은 실생활 문제들이 포함된다. 예를 들어 선형계획, 최대공약수, maximum matching을 구하는 문제 등이 P에 속한다. 2002년에는 주어진 숫자가 소수인지 아닌지 판별하는 것도 P에 속한다는 것이 밝혀졌다. 함수문제와 관련된 복잡도 종류에는 FP가 있다.

P는 흔히 '효율적으로 계산할 수 있는' 또는 '다룰 수 있는' 계산 문제들의 집합이라고 생각한다. 그러나 RP 나 BPP 같이 효율적인 풀이가 존재하는 더욱 거대한 집합이 존재한다. 또한, P에 속해있지만 실제로는 거의 비효율적인 풀이만 존재하는 문제도 있다. 예를 들어 n^1000000 번의 연산이 필요한 풀이는 실행시간은 다항시간이지만, 실제로는 매우 비효율적이다. 자세한 내용은 P-NP 문제 항목에서 다룬다.

[편집] 다른 복잡도 종류와 연관성

P를 일반화한 것이 NP이다. NP는 비결정론적 튜링 기계에서 다항시간에 판정할 수 있는 문제들의 집합이다. P는 당연히 NP의 부분집합이다. 전산학의 가장 유명한 미해결 문제 중의 하나는 P = NP인가 하는 것이다. 자세한 내용은 P-NP 문제에 있다..

P는 L보다 작지는 않은 것으로 추정된다. L은 메모리 공간의 로그 함수 만큼만 사용하여 판정할 수 있는 문제들의 집합니다. O(log n) 만큼의 공간을 이용하는 튜링 기계는 가장 많은 상태 천이를 한다고 하여도 경우의 수가 2^{O(log n)}=n^O(1) 보다 많은 시간을 사용할 수 없기 때문에, L은 P의 부분집합이다. L = P인지도 중요한 미해결 문제중의 하나이다. P = ALOGSPACE이라는 것은 알려져있다. ALOGSPACE는 alternating 튜링 기계가 로그만큼의 메모리를 써서 풀 수 있는 문제들의 집합이다. P가 PSPACE보다 크지 않다는 것도 알려져 있다. PSPACE는 다항공간을 사용하여 판정할수 있는 문제들의 집합이다. 마찬가지로P = PSPACE인지도 미해결문제이다. 요약하면 다음과 같다.

여기서 EXPTIME은 지수 시간에 풀 수 있는 문제들의 집합이다. 위에서 설명한 여러가지 복잡도 종류 중에서 다음 두 가지만 진부분집합 관계가 성립한다는 것이 알려져 있다.

• P는 EXPTIME의 진부분집합이다. 결론적으로, 모든 EXPTIME-hard 문제들은 P의 바깥에 존재한다. 또한 위 관계에서 P 오른쪽에 있는 포함관계중에서 최소한 하나는 진부분집합 관계이다. (사실 위 세가지 포함관계 모두 진부분집합 관계인 것으로 추정된다.)
• L은 PSPACE의 진부분집합이다.

P에 속한 가장 어려운 문제는 P-complete 문제이다.

P를 일반화 한 것에는 P/poly도 있다. P/poly는 비균일 다항시간(非均一 多項時間, Nonuniform Polynomial-Time)이라고도 한다. P/poly에 속한 문제는 입력의 길이에 의존하는 advice string이 주어지면 결정론적 다항시간에 풀 수 있다. 그러나 NP와 달리 다항시간기계가 검증기계가 아니므로 거짓 advice string인지 찾아낼 필요는 없다. P/poly는 거의 모든 효율적인 알고리즘을 포함하는 큰 집합이다. 모든 BPP도 P/poly에 포함된다. 만약 NP도 P/poly에 포함되면, 다항위계 전체가 오직 두 단계로 줄어든다. 반면에, 모든 판정불가능 문제들의 unary version 같은 일부 판정불가능 문제도 P/poly에 포함된다.

[편집] 성질

다항시간 알고리즘은 합성(composition)에 대해 닫혀있다. 직관적으로 설명하면, 다항시간안에 실행되는 함수를 만들어서 이 함수를 상수번 만큼 불러서 사용하고, 함수를 불러서 사용하는 알고리즘도 다항시간의 시간이 걸리면 전체 실행시간은 여전히 다항시간이다. 이런 이유로 P는 자기 자신에 대해서 낮다. 이런 이유로 P는 어떤 기계에서 정의되든지 같은 계산 능력을 가진다. 예를 들어서 랜덤 억세스가 가능한 특정한 기계는 메모리에 접근하는 다항시간 과정을 메모리에 순서대로 접근하는 다항시간으로 흉내낼 수 있기 때문에 순차접근 기계를 합성하여 랜덤 억세스 기계를 만들 수있다.

[편집] 참고문헌

• C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0201530821.
• Complexity Zoo: P, P/poly
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 34.1: Polynomial time, pp.971–979.
• Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, ISBN 0-534-94728-X. Section 7.2: The Class P, pp.234 – 241.

주요 복잡도 종류 (더 보기)
P | NP | Co-NP | NP-C | Co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C EXPTIME | EXPSPACE | PR | RE | Co-RE | RE-C | Co-RE-C | R | BQP | BPP | RP | ZPP | PCP | IP | PH