NP困難問題は実は解ける？「理論と実践の違い」を実例で解説

NP-Overrated

大学でNP困難問題は理論上は解けるが実用上は高コストだと学んだが、実際には多くの問題が実用的に解かれている。依存関係解決や型チェックは最悪ケースが発生せず、スケジューリングや巡回セールスマン問題は最適解を現実的な時間で見つけるツールが存在する。SATもAmazonが1日10億件のSMT問題を解いており、アルゴリズムの進歩がハードウェアの進歩を上回っている。最悪ケースに直面してもタイムアウトなどの対処法がある。