P-완전

계산 복잡도 이론에서 복잡도 종류 P-완전은 판정 문제의 집합으로, 병렬 컴퓨터가 빠르게 풀 수 있는 문제들을 분석하는 데 쓸모가 있다. 어떤 판정 문제가 P-완전이려면 P에 대해 완전해야 한다. 이는 P에 들어 있는 모든 문제가 프로세스 다항 개가 있는 병렬 컴퓨터로 다항로그 시간을 써서 이 문제로 환산될 수 있다는 뜻이다. 다시 말해서, 어떤 문제 A가 P-완전이려면 P 문제 B마다 B가 A로 병렬 프로세서O(n^k)개 써서 O((log n)^c) 시간에 환산될 수 있는 상수 c와 k가 있다는 뜻이다. 병렬 프로세서의 정의는 NC를 참고하라.

동기

순차 컴퓨터에서 "다룰 수 있는" 모든 문제를 포함하는 복잡도인 P는 병렬 컴퓨터에서 다룰 수 있는 문제로 구성된 복잡도 NC도 포함한다. 이는 순차 기계가 병렬 컴퓨터를 시뮬레이트할 수 있기 때문이다. NC=P인지는 아직 밝혀지지 않았다. 다시 말해서, 원래 순차적인, 다룰 수 있는 문제가 존재하는지 여부는 아직 모른다. 다만, P와 NP가 다를 가능성이 높기 때문에 NC와 P도 다를 것으로 추측한다.

NP-완전은 "다룰 수 없을 것 같은" 문제들의 집합으로 P=NP 문제를 연구하면서 나온 개념이다. 비슷하게, "병렬화할 수 없을 것 같은", "원래 순차적인 것 같은" 문제의 집합인 P-완전 문제는 NC=P 문제와 관련이 있다. 어떤 P-완전문제를 빠르게 병렬화하는 방법을 찾는다면, NC ≠ P 명제가 틀리다는 것을 증명하게 된다.

P-완전 문제들

가장 기본적인 P-완전 문제는, 튜링 기계와 여기 들어가는 입력이 하나 있고, 일진수 $T$가 있을 때, 이 기계가 첫 $T$ 단계 안에 멈출 것인가 하는 문제이다. 이 문제가 P-완전임은 틀림없다. 만약 순차 컴퓨터의 일반적인 시뮬레이션을 병렬화할 수 있다면, 그 컴퓨터에서 돌아가는 어떠한 프로그램도 병렬화할 수 있을 것이기 때문이다. 이 문제가 NC라면 P에 들어가는 다른 모든 문제도 NC가 된다. 단계 수가 일진이 아니라 이진수라면 이 문제는 EXPTIME-완전이 된다.

위 보기는 P-완전 이론에서 흔히 쓰는 방법이다. 어떤 문제를 병렬 컴퓨터가 빨리 풀어내는지는 진정한 관심사가 아니다. 다만 병렬 컴퓨터가 그 문제를 순차 컴퓨터보다 훨씬 더 빨리 푸는지만 관심이 있을 뿐이다. 따라서 그 문제를 순차 버전은 P가 되도록 바꾸어 불러야 한다. 이것이 T가 일진수여야 하는 까닭이다. $T$가 이진수(0과 1이 $n$개로 이루어진 문자열, $n=\log T$)라면 순차 알고리즘은 2ⁿ 시간 걸린다. 반면에 $T$가 일진수(1이 $n$개로 이루어진 문자열, $n=T$)라면 순차 알고리즘은 $n$시간 걸릴 뿐이다. $T$를 이진이 아닌 일진수로 씀으로써 순차 알고리즘에 걸리는 시간을 지수 시간에서 선형 시간으로 줄이게 된다. 이리하여 순차 문제는 P에 들게 된다. 이 문제는 병렬화할 수 있을 때만 NC가 된다.

이밖에도 P-완전임이 증명된, 즉, 원래 순차적인 문제는 많이 있다. 아래 나열하는 문제는 판정 문제꼴로 되어 있다.

• 선형계획법 - 선형 부등식 제약조건을 만족하면서 선형 함수를 최대화하는 문제.
• 깊이 우선 탐색 순서 - 순서가 정해진 인접 리스트로 표현되는 그래프에 마디 u와 v가 있다고 할 때, 깊이 우선 탐색에서 꼭짓점 u를 v보다 먼저 방문하는지를 묻는 문제.
• 문맥 자유 문법 - 문맥 자유 문법과 문자열 하나가 있을 때, 이 문자열을 그 문법으로 만들 수 있는가?

어떤 문제가 P-완전인지 증명하려면 보통, 이미 알고 있는 P-완전 문제를 좋은 병렬 알고리즘을 써서 그 문제로 환산해 본다.

P-완전인지 밝혀지지 않은 문제

어떤 문제는 NP-완전, P 어느 쪽인지 아직 밝혀지지 않았다. 이 문제들(예: 소인수 분해)은 어려울 것으로 추측하고 있다. 이와 비슷하게 P-완전인지 NC인지 밝혀지지 않았지만, 어려울 것으로 보고 있는 문제들도 있다.

예를 들어 두 이진수의 최대공약수를 찾는 문제의 판정 문제꼴이나, 확장 유클리드 알고리즘이 이진수 두 개를 입력받았을 때 어떤 답을 할지 판정하는 문제가 있다.

참고 문헌

• 그린로, 레이먼드, 제임스 후버, 월터 루조 (1995). 《Limits To Parallel computation; P-Completeness Theory》 (영어). ISBN 0-19-508591-4.  CS1 관리 - 여러 이름 (링크) — 이론을 전개하고 P-완전 문제 96개에 대한 목록을 만들었다.
• Satoru Miyano, Shuji Shiraishi, and Takayoshi Shoudai. A List of P-Complete Problems. Kyushu University, RIFIS-TR-CS-17. December 1990.