복잡도 클래스 P (complexity class P)
쉽게 풀면
클래스 P는 '효율적으로 풀 수 있다'고 여겨지는 문제들의 모임이다. 여기서 '효율적'이라는 것은 입력이 커져도 걸리는 시간이 입력 크기의 거듭제곱 정도로만 늘어난다는 뜻이다. 정렬, 최단 경로 찾기, 두 수의 최대공약수 구하기 등이 P에 속하는 대표적인 문제들이다. 컴퓨터과학에서는 흔히 P에 속한 문제를 '현실적으로 풀 수 있는 문제'로 취급한다.
왜 중요한가
클래스 P는 계산 복잡도 이론에서 '효율적으로 계산 가능하다'는 개념을 정의하는 기준점 역할을 한다. 새로운 문제가 등장했을 때 이를 P 안에 넣을 수 있는지, 아니면 NP-완전처럼 더 어려운 클래스에 속하는지를 가리는 작업은 알고리즘 설계뿐 아니라 암호학, 최적화, 게임 이론 등 여러 응용 분야에서 이론적 한계를 판단하는 출발점이 된다. 특히 P와 NP가 같은 클래스인지를 묻는 P-NP 문제는 이론컴퓨터과학 전체에서 가장 근본적인 미해결 질문으로 꼽히기 때문에, 어떤 문제를 P로 환원하거나 P에 속함을 증명하는 논문은 그 자체로 이론적 의미를 가진다.
논문에서는 이렇게 쓰입니다
어떤 알고리즘의 효율성을 클래스 P 소속 여부로 요약해 설명할 때 사용된다.
조합 최적화나 그래프 이론 논문에서, 다루는 문제의 난이도를 이미 잘 알려진 문제로의 환원을 통해 P와의 관계 속에서 논증할 때 쓰이는 표현이다.
인공지능이나 자연어처리 분야에서 어떤 추론·질의 절차가 다항 시간 안에 끝난다는 것을 보여 확장 가능성을 주장할 때 사용되는 문장 패턴이다.
조금 더 깊게 보면
실제로 어떤 문제가 P에 속함을 보일 때는 대개 두 가지 방법 중 하나를 쓴다. 하나는 다항 시간에 동작하는 알고리즘을 직접 제시하는 것이고, 다른 하나는 이미 P에 속한다고 알려진 문제로 다항 시간 환원(polynomial-time reduction)을 구성하는 것이다. 또한 논문에서는 P를 이야기할 때 종종 NP, co-NP, PSPACE 같은 인접 클래스와의 포함 관계를 함께 언급하는데, 이는 어떤 문제의 난이도를 상대적으로 자리매김하기 위해서다. 다만 클래스 P는 어디까지나 점근적(입력이 충분히 커질 때) 효율성을 다루는 개념이므로, 실제 구현에서의 상수항이나 작은 입력에서의 성능과는 별개로 이해해야 한다.
주의할 점
다항 시간이라도 지수가 매우 크면(예: n^100) 실제로는 비효율적일 수 있어, P 소속이 곧 실용적 빠름을 보장하지는 않는다.