下文中,
指要进行全排列的字符串, 是 中包含的字母集合
- 如果按照那个“存在一个验证器,其在多项式时间内验证答案”,全排列算法似乎难以找到一个长度为
的证据 - 但是,确实可以有一台NTM在多项式时间内运行全排列算法:从start stat开始,每一步都非确定性的猜测下一个字符,那么,经过
步后,就可以生成 个串,每个NTM分支都验证自己生成的这个串是不是合法的 的一个全排列,如果是,accept(从而有 个接受分支),那么接受分支上的字符串就是全排列的结果。consider that,不同分支生成的字符串必然是不同的,所以不需要对所有结果进一步处理就可以得到结果。 - 备注:多个接受分支是合法的,以下句子暗示可以有多个接受分支。
书上P48 倒数第一句:The machine accepts if at least one of the computation branches ends in an accept state, as shown in Figure 1.28
- (此处NTM似乎可能存在问题——该算法的运行结果是所有接受分支上的字符串,这是否是合法的)
- 那么,全排列算法是否属于NP?