Introduction 우리는 P문제와 NP문제를 정의를 알아보았다. 2021/01/24 - [IT/Algorithms] - Class P & Class NP 간단히 다시 정리하자면 아래와 같다. P문제 - 다항시간안에 풀 수 있는 판별문제 (결정적/비결정적 알고리즘 모두) NP문제 - 비결정적 알고리즘으로 다항시간안에 풀 수 있는 판별문제 P문제는 우리에게 익숙한 결정적 알고리즘으로 해결이 가능한 문제들이다. 그리고 P문제는 비결정적 알고리즘으로도 충분히 해결이 가능한 문제이다. (결정적 알고리즘은 비결정적 알고리즘의 조금 특수한 경우) 따라서 ClassP로 분류된 문제들은 Class NP에도 포함된다. (예를 들어, 합성수 판별문제는 P문제이면서 동시에 NP문제이다.) 위 그림은 Class P와 Cl..
