close
若一個Problem不能在polynomial Time
的時間內解決的話(像是exponential 或super-polynomial time),
這個問題就稱為intractable.
而定義polynomial Time 為"Practically feasible computation"是沒
有爭論的,因為:
1.任何的polynomial 的成長速度,最後都會被exponential所超過.
2.n80以及2n/100這主極端的例子,在實際上是很少發生的.
而另外一個爭論是:對於發生exponential Time的problem,
可能都是出現在少數的input上面,但是我們並不考量此點,
因為:
1.我們並無法預先得知input distribution.
2.我們有可能在解決特定的一個instance,而它正好是所謂的少數狀況.
全站熱搜
留言列表
Software (5)
