P-완전

3. P-완전 문제들

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

이는 P-완전 이론에서 흔히 쓰는 방법으로, 어떤 문제를 병렬 컴퓨터가 빨리 풀어내는지는 관심사가 아니다. 다만 병렬 컴퓨터가 그 문제를 순차 컴퓨터보다 ''훨씬 더'' 빨리 푸는지만 관심이 있을 뿐이다. 따라서 그 문제를 순차 버전은 P가 되도록 바꾸어 불러야 하며, 이것이 ''T''가 일진수여야 하는 까닭이다.

이밖에도 P-완전임이 증명된, 즉 원래 순차적인 문제는 많이 있다. 이 문제들은 판정 문제 꼴로 되어 있으며, 어떤 문제가 P-완전인지 증명하려면 보통 이미 알고 있는 P-완전 문제를 좋은 병렬 알고리즘을 써서 그 문제로 환산해 본다.

3. 1. P-완전으로 증명된 문제

• 선형계획법: 선형 부등식 제약 조건을 만족하면서 선형 함수를 최대화하는 문제이다.
• 깊이 우선 탐색 순서: 순서가 정해진 인접 리스트로 표현되는 그래프에 마디 ''u''와 ''v''가 있을 때, 깊이 우선 탐색에서 꼭짓점 ''u''를 ''v''보다 먼저 방문하는지를 묻는 문제이다.
• 문맥 자유 문법: 문맥 자유 문법과 문자열 하나가 있을 때, 이 문자열을 그 문법으로 만들 수 있는가?
• 회로 값 문제(CVP): 불리언 회로가 주어지면, 회로의 입력과 회로의 하나의 게이트가 주어지면, 해당 게이트의 출력을 계산한다.
• CVP의 제한된 경우: CVP와 유사하지만, 각 게이트는 두 개의 입력과 두 개의 출력(F와 Not F)을 가지며, 모든 다른 레이어는 AND 게이트이고 나머지는 OR 게이트이다 (또는 동등하게, 모든 게이트는 NAND 게이트 또는 모든 게이트는 NOR 게이트이다). 게이트의 입력은 바로 앞의 레이어에서 가져온다.
• 혼-만족성: 혼 절 집합이 주어지면, 이를 만족하는 변수 할당이 있는가? 이것은 불리언 만족성 문제의 P 버전이다.
• 생명 게임: 콘웨이의 생명 게임의 초기 구성, 특정 셀 및 시간 ''T'' (일진법)이 주어지면, 해당 셀이 ''T'' 단계 후에 살아 있는가?
• LZW (알고리즘) (1978 패러다임) 데이터 압축: 문자열 ''s''와 ''t''가 주어지면, LZ78 방법으로 ''s''를 압축하면 ''t''가 사전에 추가되는가? ([gzip]]과 같은 LZ77 압축의 경우, 이 문제는 "''t''가 ''s''에 있는가?"로 축소되므로 훨씬 쉽다.)
• 부분 유형에 대한 유형 추론: 유형 이론에서 람다 계산에서 유형이 지정되지 않은 항이 주어지면, 이 항이 부분 유형을 갖는지 여부를 결정한다.

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

4. P-완전 문제의 다른 시간 복잡도

P-완전 문제는 다른 시간 복잡도로 해결될 수 있다. 예를 들어, 회로 값 문제는 선형 시간에 위상 정렬로 해결될 수 있다.^[1] 물론, P-완전 문제로의 감소는 다른 시간 복잡도를 가질 수 있기 때문에, 이 사실이 P의 모든 문제가 선형 시간으로 해결될 수 있음을 의미하지는 않는다.

5. P-완전성과 희소 언어

1999년, 진-이 차이(Jin-Yi Cai)와 D. 시바쿠마(D. Sivakumar)는 오기하라(Ogihara)의 연구를 바탕으로 P-완전인 희소 언어가 존재한다면 L = P임을 보였다.