💡Intractability 사전적인 의미로는 취급하거나 작업하기 어렵다는 뜻이다. CS적인 관점에서는 문제가 Intractable하다는 뜻은 polynomial-time-algorithm(다차시간 알고리즘)으로 못푼다는 의미이다. polynomial-time algorithm은 최악 시간복잡도의 상한이 입력크기의 다항식 함수가 되는 알고리즘이다. 다루기 힘든 정도는 문제를 푸는 어떤 특정 알고리즘의 성질이 아니라 문제의 성질이라는 사실을 반드시 알아야한다. 다루기 힘든 정도에 대하여 3가지 종류로 문제를 분류할 수 있다. 1.다차시간 알고리즘을 찾은 문제 2.다루기 힘들다고 증명된 문제 3.다루기 힘들다고 증명되지도 않았지만, 다차시간 알고리즘도 찾지 못한 문제(NP-complete) 예를 들어 TSP..
