P (polynomial time)
다항 시간 안에 「풀 수 있는」 결정 문제의 모임
보통의(결정적) 튜링 기계가 다항 시간에 답을 내는 결정 문제의 모임이다. 두 지점이 길로 이어져 있는지, 2-SAT 식이 충족 가능한지, 주어진 수가 소수인지(2002년에 증명됨) 같은 문제가 여기에 든다. P 의 문제는 답을 직접 구해 보면 검증도 되므로 P ⊆ NP 다. 거꾸로 NP ⊆ P 인지, 곧 P = NP 인지가 미해결 문제다.