請問複雜性問題
書上的意思好像是說..
任何一個問題可以轉化為一個判定問題(decision problem)
而判定問題可以用一個L (language)來解釋(或表示)
所以說處理一個判定問題就是處理一個語言識別問題
當一個判定問題 存在一個可以在多項式時間內被解決的演算法
==>表示一種代表這種判定問題的語言 可以在多項式時間內被識別
另外, P類問題是表示:存在一種多項式時間的演算法可解決的問題的集合
書本上定義說 P= 存在一個多項式時間的演算法可識別的L(language)
所成的集合
所以結論:判定問題就是語言識別問題?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.59.211.123
※ 編輯: ikjhyu 來自: 61.59.211.123 (05/29 21:03)
推
218.161.1.43 05/30, , 1F
218.161.1.43 05/30, 1F
推
61.59.211.123 05/31, , 2F
61.59.211.123 05/31, 2F
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
