NP-Zor

NP-Zor (NP-Hard) sınıfı, bilgisayar bilimleri karmaşıklık teorisinin temel kategorilerinden biridir ve NP sınıfındaki her problemin polinom-zamanda kendisine indirgenebildiği problemleri kapsar. Kavramın temelini Cook (1971) Boole sağlanabilirliği problemini (SAT) NP-tam olarak göstererek atmış, Karp (1972) yirmi bir kombinatoryel problemin NP-tamlığını polinom-zaman indirgemeleriyle kanıtlayarak kategoriyi pratik OR alanına taşımıştır. Bir problem hem NP'de hem de NP-Zor ise NP-Tam (NP-Complete) sınıfındadır; problem NP'de değilse sadece NP-Zor olabilir (örneğin TSP'nin optimizasyon versiyonu). Klasik NP-Zor problemler şunları içerir: gezgin satıcı (TSP), sırt çantası (knapsack), graph coloring, set covering, vehicle routing, job shop scheduling, makespan minimization, bin packing ve birçok karma tamsayılı programlama (MIP) formülasyonu. P = NP eşitliği açık bir matematiksel sorudur; pratikte ise NP-Zor problemler için bilinen tüm tam algoritmalar problem boyutuyla üstel zaman alır. Bu durum sezgisellerin (heuristic), metasezgisellerin ve approximation algoritmaların doğmasına neden olmuştur. Garey ve Johnson (1979) NP-tamlık kanıtları için referans kaynaktır. Bir problemin NP-Zor sınıflandırılması, uygulamacının doğrudan tam çözüm beklentisini bırakıp gevşetme, ayrıştırma veya sezgisel yaklaşımları seçmesi için kritik bir sinyaldir.