问题1:如果P=NP,那么是否所有在P里的问题都可以互相化约?
我原本认为是可以,利用NP完全的问题的特性就可以互相化约,但是好像无法将NP完全问题转化为任意的P问题
现在更倾向于否了,但是还没找到反证,不知道有没有人能提供帮助。
问题2:已知某可计算函数f的值域有限,那么输入任何值,这个值是否在值域以内是否是可判定的?
我认为是否,但是还无法严谨的证明。
问题3:对于下面两个形式语言:
EQUAL{x,y : x,y是有效的图灵机编码,并且x,y接受的语言相等}
和
MIN {x :x是有效的图灵机编码,并且x的编码是最简的(相对于其他接受同样语言的图灵机而言)}
这两个语言是否能相互化约?
EQUAL < MIN很简单,但是反过来 MIN < EQUAL似乎不可能
我原本认为是可以,利用NP完全的问题的特性就可以互相化约,但是好像无法将NP完全问题转化为任意的P问题
现在更倾向于否了,但是还没找到反证,不知道有没有人能提供帮助。
问题2:已知某可计算函数f的值域有限,那么输入任何值,这个值是否在值域以内是否是可判定的?
我认为是否,但是还无法严谨的证明。
问题3:对于下面两个形式语言:
EQUAL{x,y : x,y是有效的图灵机编码,并且x,y接受的语言相等}
和
MIN {x :x是有效的图灵机编码,并且x的编码是最简的(相对于其他接受同样语言的图灵机而言)}
这两个语言是否能相互化约?
EQUAL < MIN很简单,但是反过来 MIN < EQUAL似乎不可能