NP-난해 문제는 실제로는 풀 수 있다
NP-Overrated
대학에서 NP-난해 문제가 이론적으로는 풀 수 있지만 실제로는 불가능에 가깝다고 배웠을 것이다. 하지만 이 글은 그런 인식이 실무에서는 대부분 무의미하다고 주장한다. 의존성 해결, 타입 검사, 스케줄링, 외판원 문제, SAT 등 대표적인 NP-난해 문제들이 실제로는 빠르게 해결되는 경우가 많으며, 최적해를 보장하는 도구들도 존재한다. 1991년부터 2015년 사이 알고리즘 개선으로 4,500억 배의 성능 향상이 있었고, Amazon은 하루에 10억 개의 SMT 문제를 해결한다. 최악의 경우에도 타임아웃과 오류 메시지로 대처하면 된다.
이론적으로는 이론과 실무 사이에 차이가 없다. 그러나 실무에서는 차이가 있다.