P는 계산 복잡도 이론(computational complexity theory)에서 다루는 핵심적인 복잡도 종류(complexity class) 중 하나로, 결정적 튜링 기계(deterministic Turing machine)를 사용하여 다항 시간(polynomial time) 안에 해결할 수 있는 모든 결정 문제(decision problem)의 집합을 가리킨다. PTIME 또는 DTIME(n^O(1))이라고도 불린다.
정의
언어 L이 P에 속한다는 것은 다음과 같은 조건을 만족하는 결정적 튜링 기계 M이 존재함을 의미한다.
- M은 모든 입력에 대해 다항 시간 안에 동작한다.
- L에 속하는 모든 입력 x에 대해 M은 1을 출력한다.
- L에 속하지 않는 모든 입력 x에 대해 M은 0을 출력한다.
즉, 입력의 크기 n에 대해 실행 시간이 어떤 다항식 n^k (k는 상수)에 의해 상한이 정해지는 문제들의 집합이다.
의의와 배경
P는 "효율적으로 풀 수 있는"(tractable) 문제들의 집합으로 간주되며, 이러한 관점은 코햄의 논제(Cobham's thesis)로 알려져 있다. 이는 대략적인 규칙으로, 실제로는 P에 속하지 않으면서 실용적으로 풀 수 있는 문제나, 반대로 P에 속하면서도 현실적으로는 비효율적인 문제가 존재할 수 있다.
다항 시간 알고리즘은 합성(composition)에 대해 닫혀 있어, 다항 시간 알고리즘을 결합해도 여전히 다항 시간 알고리즘이 된다. 이러한 특성 때문에 P는 기계 독립적(machine-independent)인 종류로 간주된다.
주요 사례
P에 속하는 대표적인 자연 문제로는 선형 계획법(linear programming)의 결정 버전, 최대 매칭(maximum matching) 문제 등이 있다. 2002년에는 어떤 수가 소수인지를 판별하는 문제(primality testing)가 P에 속한다는 것이 증명되었다(AKS 알고리즘). 함수 문제의 관련 종류는 FP로 표기된다.
다른 복잡도 종류와의 관계
P는 NP의 부분집합이며, 대부분의 학자들은 P가 NP의 진부분집합(proper subset)이라고 추정하지만, 이는 여전히 증명되지 않은 미해결 문제이다(P ≠ NP 문제). 이 외에도 다음의 포함 관계가 성립한다.
L ⊆ AL = P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME
이 중에서 P가 EXPTIME의 진부분집합이라는 것과 L이 PSPACE의 진부분집합이라는 것은 증명되어 있으나, P와 NP, P와 PSPACE 사이의 포함 관계가 엄격한지는 알려져 있지 않다.
P는 대수 공간(로그 공간)에서 결정 가능한 문제들의 종류인 L을 포함하며, P = AL(교대 튜링 기계로 로그 공간에서 해결 가능한 문제들의 집합)이 성립함이 알려져 있다. 또한 P는 BQP에 포함되며 이 포함 관계가 엄격한지는 알려져 있지 않다.
역사
다항 시간이라는 개념의 도입은 코햄(Alan Cobham)과 에드먼즈(Jack Edmonds)의 공로로 일반적으로 인정받고 있으며, 라빈(Michael Rabin)도 독자적으로 유사한 시기에 이 개념을 고안한 것으로 알려져 있다. 코햄은 효율적 알고리즘을 특징짓는 강건한 방법으로 이 종류를 도입했다. 다만 이보다 훨씬 이른 1910년, 포클링턴(H. C. Pocklington)이 어떤 알고리즘의 실행 시간을 "계수의 로그의 거듭제곱에 비례"하는 것과 "계수 자체 또는 그 제곱근에 비례"하는 것으로 대비하여 서술한 기록이 있어, 다항 시간과 (중간 정도의) 지수 시간의 구분이 훨씬 일찍 암묵적으로 이루어졌음을 보여 준다.
기술적 특성
P에 속하는 언어들은 여집합(complement), 역전(reversal), 교집합, 합집합, 연결(concatenation), 클레이니 폐포(Kleene closure), 역준동형사상, 상보성 연산에 대해 닫혀 있다.
일부 문제는 다항 시간 안에 풀 수 있음이 비구성적(nonconstructive)으로 증명되어 있으나 구체적인 알고리즘은 알려지지 않은 경우가 있다. 예를 들어 로버트슨-시모어 정리(Robertson-Seymour theorem)는 토러스에 임베딩 가능한 그래프를 판별하는 다항 시간 알고리즘의 존재를 보장하지만, 구체적인 알고리즘은 알려져 있지 않다.
서술적 복잡도(descriptive complexity) 이론에서는 P가 순서 구조에서 최소 고정점 연산자를 갖춘 1차 논리(FO(LFP))로 표현 가능한 문제들의 집합과 일치함이 알려져 있다.
P에서 가장 어려운 문제들은 P-완전(P-complete) 문제라고 불린다.
