Introduction 계산복잡도는 알고리즘의 특성이지 우리가 풀고자 하는 문제 그 자체의 특성은 아니다. 즉 문제는 하나지만, 문제에 대해 다른 복잡도를 가지는 다수의 알고리즘이 존재할 수 있다. 효율적인 알고리즘에 찾는것에 무게를 두는 것이 아니라 문제의 본질 그 자체에 관심을 두고를 연구하는 학문이 있다. 이 학문에서는 문제들을 문제의 해결 난이도에 따라 분류하고 분류된 문제들의 특성을 연구한다. Tractable? Intractable? 계산복잡도 이론에서 문제의 난이도는 그 문제를 해결하는 빠른 알고리즘의 존재유무에 달려있다. 그리고 빠른 알고리즘은 다항시간(polynomial time)안에 답을 찾는 알고리즘을 말한다. 다항시간내에 풀 수 있는 알고리즘이 존재한다면, 해당 문제를 Tractab..