NP-난제는 과장된 위협일 수 있다
원제 NP-overrated
235 포인트댓글 164
Key Point
NP-난제의 실질적 해결 가능성에 대한 통념을 깨는 내용으로, 이론과 실제 간극에 대한 개발자들의 오해를 바로잡는 데 실질적 가치가 있다.
핵심 요약
- NP-난제 문제는 이론상 풀 수 없지만 현실에서는 99.9%의 입력값에서 빠른 해답을 제공할 수 있다.
- 패키지 의존성 해결과 타입 체킹 같은 NP-난제는 실제로 최악의 경우가 나타나지 않으며 SAT 문제도 알고리즘 개선으로 해결되고 있다.
- 1991년부터 2015년까지 알고리즘 최적화가 하드웨어 성능 향상을 450억 배 능가했으며 최악의 경우에는 타임아웃 처리로 대응할 수 있다.