NP-zor problemler aslında o kadar da zor değil

NP-overrated

Üniversitede NP-zor problemlerin pratikte çözülemez olduğunu öğrendik, ama bu algı yanlış. Teori, en kötü durumda algoritmaların patlayacağını söyler; ancak pratikte bu durum nadiren oluşur. Paket yöneticileri, tip kontrolü, çizelgeleme, Gezgin Satıcı ve SAT gibi problemler, gelişmiş algoritmalar ve araçlarla (Gurobi, SCIP, OR-Tools) makul sürede çözülebiliyor. Amazon günde bir milyar SMT sorgusu çözüyor. Algoritmik hızlanma, donanım gelişimini geride bıraktı; 1991-2015 arasında 450 milyar kat hız artışı sağlandı. En kötü durumda bile timeout ve hata mesajı gibi pratik çözümler var.