Polynomial Time Algorithm

Zero-knowledge proof를 학습하던 중, P/NP에 관한 개념이 나와 이를 정리해본다.

TL;DR

Polynomial Time Algorithm(다항시간 알고리즘)은 간단히 말해, '어떤 문제'에 대해, 다항시간 내에 해결할 수 있는 알고리즘이 존재한다면, '그 문제'는 Class P 집합에 속한다.

Class NP란?

어떠한 문제의 입력이 주어졌을 때, 다항시간 내에 해결책이 맞는지 검증하는 알고리즘이 존재하는 문제의 집합을 말한다.

가령, 주어진 자연수를 인수분해하는 문제는 다항시간 내에 해결될 수 있는 알고리즘이 존재하지 않으며, 해당 문제를 해결하는 데에는 지수시간(𝑂(rⁿ)) 이상의 복잡도가 필요하다. 따라서 해당 문제는 Class NP에 속한다.

Class P란?

어떠한 문제를 다항시간 내에 해결할 수 있는 알고리즘이 존재하는 decision problems의 집합을 말한다.

가령, 주어진 숫자에 대해 소수인지 판별하는 문제는 𝑂(√n) 이므로 다항시간(𝑂(n^k), 단 k는 상수) 내에 해결될 수 있으며 Class P에 속한다. (cf. 소수를 찾는 문제는 decision problems이 아니므로, Class P/NP에 속하지 않는 문제다.)

참고로 Class P는 Class NP의 부분집합이다.