P, NP, reductions ve alt sınırlar

P, karar problemlerinin polinom zamanda çözülebildiği sınıftır. NP, evet cevabının polinom boyutlu certificate ile polinom zamanda doğrulanabildiği sınıftır; “non-polynomial” kısaltması değildir. P⊆NP, P=NP olup olmadığı açık problemdir. NP-complete hem NP içindedir hem NP-hard'dır. NP-hard problemin NP'de olması gerekmez; optimization ve undecidable örnekler dahil olabilir.

Reduction A≤pB, A'nın örneğini B'ye polinom zamanda dönüştürür. B için hızlı solver varsa A'yı çözeriz. B'nin zor olduğunu kanıtlamak için bilinen zor A'dan B'ye indirgeme yap; ters yön tek başına işe yaramaz. TSP karar sürümü ile en kısa turu bulma optimization sürümünü ayır.

NP-hard “hiçbir girdi çözülemez” veya “evren bitene kadar sürer” demek değildir. Küçük n, özel grafik sınıfları, parametreler veya pratik branch-and-bound işe yarayabilir. Pseudo-polynomial algoritmalar sayı büyüklüğüne bağımlıdır; binary encoding yüzünden polinom bit maliyeti olmayabilir. Undecidability ise karmaşıklıktan farklıdır: tüm girdiler için karar veren algoritmanın yokluğunu anlatır.

Reduction yönünü karıştırma

SAT zor biliniyor ve yeni problem X'in zor olduğunu göstermek istiyorsun. SAT instance'ını X instance'ına polinom zamanda dönüştür; SAT evet ⇔ X evet eşdeğerliğini kanıtla. Bu SAT≤pX'tir. Yalnız X≤pSAT göstermek X'in zor olduğunu göstermez: kolay problemler de SAT'e indirgenebilir.

Bir problemin NP-complete olduğunu göstermek iki ayrı yükümlülük getirir: (1) polynomial certificate verification ile NP üyeliği; (2) bilinen NP-hard problemden reduction. Optimization problemi için “NP-complete” sözcüğünü karar sürümü belirtilmeden kullanmak terminolojik belirsizlik üretir. Karar sürümünde threshold vardır: örneğin cost≤K tur mevcut mu?

Input encoding kritiktir. n sayısal değeri unary yazılırsa input length n; binary yazılırsa yaklaşık log₂ n'dir. O(n) loop binary input length bakımından üstel olabilir. “Polynomial” hangi uzunluğa göre sorusunu sormadan complexity sınıfı atanmaz.

Temel: Hamilton certificate'ını doğrulama ile arama farkını açıkla. Orta: Threshold'lu optimization karar sürümü yaz. İleri: Bir reduction için mapping, polynomial time ve iki yönlü correctness ispatını ayrı bölümlerde sun. P≠NP kanıtlandı gibi yazma; açık problem olduğunu koru.

def verify_cycle(vertices,edges,cycle):
    return len(cycle)==len(vertices) and set(cycle)==set(vertices) and all((cycle[i],cycle[(i+1)%len(cycle)]) in edges for i in range(len(cycle)))
assert verify_cycle([0,1,2],{(0,1),(1,2),(2,0)},[0,1,2])