안녕하세요. 언제나 휴일, 언휴예요. 이번에는 NP 완전(NP - Completeness) 이론에 관해 소개할게요. 1971년 스티븐 쿡(Steven Cook)과 1972년 리처드 카프(Richard Karp)는 논문을 통해 P-NP 문제를 꺼내들었죠. P는 Polynominal(다항) 시간에 문제를 풀수 있는 문제를 말해요. n 개의 자료가 있을 때 문제를 해결하는데 걸리는 시간을 n의 다항식(1, n, n^2 등)으로 표현할 수 있는 문제예요. 예를 들어 버블 정렬 알고리즘은 점근식 표기 O(n^2)으로 표현할 수 있어서 P 문제죠. 이와 같은 문제는 전산학에서 풀기 쉬운 문제 혹은 컴퓨터로 계산할 수 있는 문제라고 말합니다. NP는 문제 해결 방법을 찾는 것은 어렵지만 답을 제시했을 때 맞는지 틀리..
