안녕

이전 글의 Halting Problem을 기억하시나요? 이처럼 진위 판별을 불가능한 문제가 있고, 진위 판별이 불가능한 문제가 있습니다. 간단하게 진위 판별 문제(결정 문제)로 NP를 제한하면 이론을 전개하기가 쉬워집니다. 우선 결정 문제를 한 번 알아봅시다. 1. Decision Problem 그러기 위해선 우선 지금까지 해온 모든 알고리즘들, Decision Problem과 Optimization Problem에 대해 생각해봐야 합니다. 최적화 문제란 답이 최적해라는 말입니다. 하지만 최적화 문제는 결정 문제로 만들 수 있습니다. 참고로 결정 문제는 yes or no 두 가지 정답만 내놓습니다. 예를 들어서, TSP 문제를 생각해봅시다. 우리는 최소 거리를 구하는 알고리즘을 구현했지만, 만약 특정 거..

새로운 알고리즘을 개발할 때, 이 알고리즘이 다루기 어렵다는 것은 무엇을 의미할까요? 현실에서 다루기 어렵다는 것은 취급하기 또는 작업하기 어렵다로 정의하지만, 컴퓨터 과학에서 다루기 어렵다는 것은 "해당 문제를 다항시간(Polynomial-time)에 풀 수 없다"를 의미합니다. 즉 알고리즘의 Worst Case W(n) = O(p(n)) 만족하는 다항식 p(n)이 없다는 뜻입니다. 다항 시간안에 풀 수 있는 알고리즘은 2n, 3n^3, n lg n등이 있습니다. n lg n은 n에 대한 다항식은 아니지만, n lg n < n^2에 의하여 다항시간 알고리즘으로 분류합니다. 따라서 컴퓨터 과학에서 문제가 다루가 힘들다는 것은 특정 알고리즘의 성질이 아니라 문제의 성질이 되어야 합니다. 사실 최악 시간 복..