作者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