-
Oded Zeng
“全排列算法”也许需要先定义为语言,这样才能方便讨论。
如果你说的“全排列算法”是指图灵机要输出一个串的全排列(在纸带上留下全排列并停机),那么显然这不会是NP,因为光是存储全排列就需要用n!的复杂度。
至于你说的那个NTM,你大概意思也许是通过分支来生成全排列。但用NTM来考虑这个问题的时候并不方便,因为NTM的"输出"功能似乎没定义,而确定性图灵机的输出可以简单定义为停机时纸带留下的东西(并且这样的定义还是比较普遍的,不少书上也是如此定义)。如果你说的是“检测某个串是不是某个串的排列”,这似乎只需要比较长度和字符种类与个数就可以了。
-
-
Oded Zeng
我觉得你可以把你这里的这个U描述一下(中层描述,它的输入是什么?它要做什么,返回什么?),另外就是,通用图灵机(记为
)其实是有定义的,粗略描述为: 模拟 的计算过程。如果该计算停机,则 停机并在纸带上留下计算结果 ,否则不停机。 U在某种意义上是可以解决任意一台图灵机可以解决的问题,但它并不能解决问题本身,因为我们需要针对问题设计出对应的图灵机M,才能把M作为输入扔给U,然后U"解决"了该问题。
至于U是否复杂,这个无法衡量,因为没有衡量标准。就描述上的复杂性来看,U的描述本身是很简单的(就是模拟嘛),复杂的也许是它的输入
。。。所以需要说明是什么方面的"复杂"。 -
Oded Zeng
差不多,其实按照定义:
其中,是指长度为 的比特串集合(等于0则为空串)
也就是说,中的任意一个元素都是有限长度的。 而无穷比特序列则不属于
,因为无穷比特序列的长度是无限大的。 刚开始可能会有这样的误区: 虽然它长度无穷大,但既然是0,1比特序列,那应该是在
中的。这个违反了我们对 的定义。而且我们需要注意一下名词的使用,串(string)和序列(sequence)是不一样的,串可以任意长,但必须是有穷长的,而序列并无此需求。 也可以这样类比,自然数集可以写成
,显然自然数集是无穷集合,并且 是无限增长的,但是任意一个自然数,都是有限长度(以十进制位数作为长度依据)。而实数的话,以超越数 为例子,它小数点后面有无穷多位,长度无限。 可能需要仔细体会一下这两种不同的“无穷”。
在对角线法证实数集不可数的证明中,我们也借助了实数(尤其是无理数)长度无穷的特性,这一特性使得我们可以灵巧地构造那个产生矛盾的小数。
而对角线法不适用于证明不可数(虽然这本身就是错误的)的一个原因在于 中每一个比特串都是有限长度的,我们无法构造出一个类似的产生矛盾的比特串。 -