휴리스틱

언제나 옳은 답을 낸다거나 언제나 빨리 끝난다는 증명은 없지만 실제 사례에서 잘 듣는 풀이 방법이다. SAT 풀이 프로그램의 가지치기 규칙, 외판원 문제의 국소 탐색, 담금질 기법 등이 그 예다. NP-완전이라는 말은 최악의 입력에 관한 것이라, 현장에서 만나는 입력은 휴리스틱으로 풀리는 경우가 많다. 그렇다고 P = NP 의 증거가 되지는 않는다. 휴리스틱이 왜, 언제 통하는지를 설명하는 것도 복잡도 이론의 과제다.