Çokterimli zamanda indirgeme

Sayfanın 9 Şubat 2017 tarihinde onaylanmış olan kontrol edilmiş bir sürümü, bu revizyonu temel almıştır.

Çokterimli zamanda indirgeme, bir problemi çokterimli (polinomsal) zamanda başka bir probleme dönüştürme işlemidir. Bu durumda, ikinci problemi çokterimli zamanda çözebilirsek ilk problemi de çokterimli zamanda çözebiliriz.

Örnek

Hamilton Çemberi Problemi, Gezgin Satıcı Problemi'ne aşağıdaki şekilde indirgenebilir.