:::: MENU ::::
tractable

İnatçılık (intractability) nedir?

İ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!)