Çokterimli zamanda indirgeme

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

Ç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[değiştir | kaynağı değiştir]

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