|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 理论计算机科学 』 (http://bbs.xml.org.cn/list.asp?boardid=64) ---- [求助]关于某些图灵机语言类的问题 (http://bbs.xml.org.cn/dispbbs.asp?boardid=64&rootid=&id=43227) |
|
-- 作者：chchtheory -- 发布时间：2/11/2007 5:27:00 PM -- [求助]关于某些图灵机语言类的问题 近日读《自动机理论，语言和计算导论》，有一个问题想不明白，请问各位大侠： （1） 对于P语言类，可如下证明对于补封闭：设L属于P，设M是接受L的图灵机。修改M以接受L的补如下：引入新的接受状态q，每当M在非接收状态下停机时，新的TM就转移到状态q；让M以前的接受状态都变成非接受状态。经过修改的图灵机接受L的补，而且与M的运行时间一样，有可能多一步移动。因此，若L属于P，L的补也属于P。 但是书上说NP似乎不封闭，特别是NP完全的语言的补不属于NP。我想请问，用上一段类似的方法能不能证明NP语言类对于补运算也封闭呢？我觉得行（如果不行的话，请各位大侠讲一讲是为什么不行，我真的是不明白）。 （2）求大侠给出NP补语言类属于PS语言类的证明。（PS语言定义：此类中的语言都是带有多项式空间限制的确定型图灵机所接受的语言，有的书上把PS叫做PSPACE）。 多谢各位好心人帮忙指教！ |
|
-- 作者：Logician -- 发布时间：2/11/2007 6:05:00 PM -- （1） 注意到NTM接受一个语言的条件是“只要有一个分支接受就算接受”。所以，P问题的那种方法，无法直接用在NP问题上。因为，假设原来的NP问题的某个实例在NTM上一共产生了10分支，其中5个接受，5个拒绝。按NTM的定义，应该接受它。按定义，用于相应补问题的NTM应该拒绝相应实例，但如果按你给出的方法构造补问题的NTM，这个NTM也会接受这个实例。所以上述构造方法不适合不确定图灵机。 简单地说，就是“存在x(P(x)”的否定是“对所有的x(┐P(x))”，而非“存在x(┐P(x)”。而你提到的构造用到NTM上时，得到的却是“存在x(┐P(x)”。 （2）不会。 |
|
-- 作者：chchtheory -- 发布时间：2/12/2007 9:49:00 AM -- 真是感谢啊！这里真是很多牛人啊呵呵！ 还希望得到更多指点，还有第二题的解答，小弟先谢了！ |
|
-- 作者：huxinhuwei -- 发布时间：3/20/2007 10:21:00 AM -- 都太强了.研究的很专啊...我是微电子专业的,对计算机体系结构熟悉一点.. 理论的东东,不是很懂... |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
5,605.469ms |