作者ikjhyu (還沒想到)
看板CSSE
標題請問複雜性問題
時間Sun May 29 21:03:28 2005
書上的意思好像是說..
任何一個問題可以轉化為一個判定問題(decision problem)
而判定問題可以用一個L (language)來解釋(或表示)
所以說處理一個判定問題就是處理一個語言識別問題
當一個判定問題 存在一個可以在多項式時間內被解決的演算法
==>表示一種代表這種判定問題的語言 可以在多項式時間內被識別
另外, P類問題是表示:存在一種多項式時間的演算法可解決的問題的集合
書本上定義說 P= 存在一個多項式時間的演算法可識別的L(language)
所成的集合
所以結論:判定問題就是語言識別問題?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.59.211.123
※ 編輯: ikjhyu 來自: 61.59.211.123 (05/29 21:03)
1F：推 SHBK:你在看manber對吧^^ 218.161.1.43 05/30
2F：推 ikjhyu:ㄟ,,不是是algorithm 61.59.211.123 05/31