NP-완전 이론이란?NP-완전이론은 어떤 문제를 현실적인 시간 안에 해결할 수 있는가에 관한 이론이다.이 의문점에서 시작하여, 문제의 종류, 파생되는 여러 개념들에 대해 알아볼 것이다. 먼저 우리는 문제를 얼마나 다루기 힘드냐(해결가능성)에 따라서 분류해볼 수 있다.여기서 '다루기 힘들다'라는 말은 다항식으로 시간복잡도를 나타낼 수있는 알고리즘을 찾을 수 없는 경우를 이야기한다.우선 다루기 힘든 문제를 정의하기 전에, 풀 수 있는 문제와 풀 수 없는 문제를 정의해야 한다. 풀 수 있는가 없는가는 기존에 아는 정의와 같다. 실제로 해결할 수 있는가(해 자체를 시간이 걸려도 찾을 수 있는가)이다.이런 문제들은 보통 모순이 발생해서 풀지 못하는 경우로, 대표적인 예시는 '종료 문제'와 '힐베르트의 10번째 문..
