İnatçılık (intractability) nedir?
İlkesel olarak çözülebilen bazı hesaplama problemlerinin uygulamada(gerçek hayatta) kullanılamayacak kadar çok zaman ve bellek gerektirmesi durumunda bu tür problemlere inatçı (intractable) denir.
SAT problemi ve diğer NP-complete problemlerin intractable olduğu düşünülmektedir fakat ispatlanmamıştır.
Verimli (efficient) bir zamanda çözülebilen problemlere tractable, çözülemeyenlere intractable denmektedir.
Verimli (efficient) zamanlar: O(n) O(n log n) O(n^3 log^2 n)
Verimsiz (inefficient) zamanlar: O(2^n) O(n!)
Teşekkürler