NP-tam
Hesaplamalı karmaşıklık kuramında NP-tam hem NP hem NP-zor olan problemlerin sınıfıdır. Dolayısıyla bu sınıftaki problemler NP sınıfının en zor problemleridir. Bu problemleri polinomsal zamanda çözebilen algoritma bulunmamaktadır.
Örnekler
- İkili tatmin edilebilirlik
- Dolaşan satıcı
- Hamilton dönüşü ve Hamilton yolu
- Hamilton yolu problemi
- Cook-Levin teoremi
- Alt küme toplamı problemi
- Bağımsız küme problemi
- Düğüm kapsama problemi
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.