P는 계산 복잡도 이론에서 결정적 튜링 기계가 입력 크기의 다항식 시간 안에 해결할 수 있는 결정 문제들의 집합을 의미한다. 여기서 “다항식 시간”이란, 입력 크기 n에 대해 실행 시간이 n^k (k는 상수) 이하인 알고리즘이 존재함을 뜻한다. P는 복잡도 클래스 중 가장 기본적인 클래스 중 하나이며, 효율적인 알고리즘이 존재한다고 일반적으로 받아들여진 문제들을 포함한다.
정의
- 형식적 정의:
P = { L | 존재하는 결정적 튜링 기계 M과 상수 k가 있어, 모든 입력 x에 대해 M이 x∈L 여부를 O(|x|^k) 시간 안에 판정한다. }
주요 성질
- 닫힘성: P는 합집합, 교집합, 보완에 대해 닫혀 있다. 즉, P에 속하는 두 언어 L₁, L₂에 대해 L₁∪L₂, L₁∩L₂, ¬L₁ 역시 P에 속한다.
- 포함 관계:
- L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME 등 복잡도 클래스 사이에 포함 관계가 존재한다. 현재로서는 P = NP인지 여부가 미해결 문제이다.
- 대표적인 문제:
- 정렬 (예: 퀵정렬, 병합정렬)
- 최단 경로 문제 (다익스트라 알고리즘)
- 최대 흐름 문제 (포드–풀커슨 알고리즘)
- 2‑SAT, 그래프의 연결성 판단 등
역사
- 1960년대 초반, 알론소 체르치와 스티븐 코어스가 복잡도 클래스의 계층 구조를 제시하면서 P 개념이 정립되었다. 이후 1971년 스티븐 쿠크가 P와 NP를 명확히 구분한 논문을 발표하면서 현대 복잡도 이론의 핵심적인 틀을 제공하였다.
관련 연구
- P‑완전 문제: P 내에서 다항식 시간 감소를 통해 서로 변환 가능한 문제들로, P 안에서 가장 “어려운” 문제들을 의미한다. 일반적으로는 실제 응용에서 별다른 의미를 갖지는 않는다.
- 시간 복잡도 구분: P는 다항식 시간 알고리즘을 의미하지만, 실제 실행 시간은 차수와 상수에 크게 의존한다. 따라서 P에 속한다고 해서 항상 실용적인 효율성을 보장하는 것은 아니다.
참고 문헌
- C. H. Papadimitriou, Computational Complexity, Addison‑Wesley, 1994.
- S. A. Cook, “The Complexity of Theorem‑Proving Procedures”, Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971.
- M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP‑Completeness, W. H. Freeman, 1979.