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

İnatçılık (intractability) nedir?” te bir düşünce

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir