全排列算法是否属于NP

---

下文中，$w$指要进行全排列的字符串，$A$是$w$中包含的字母集合

• 如果按照那个“存在一个验证器，其在多项式时间内验证答案”，全排列算法似乎难以找到一个长度为$O(|w|)$ 的证据
• 但是，确实可以有一台NTM在多项式时间内运行全排列算法：从start stat开始，每一步都非确定性的猜测下一个字符，那么，经过$|w|$步后，就可以生成$|A|^{|w}$ 个串，每个NTM分支都验证自己生成的这个串是不是合法的$w$的一个全排列，如果是，accept（从而有$|A|!$个接受分支），那么接受分支上的字符串就是全排列的结果。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？

“全排列算法”也许需要先定义为语言，这样才能方便讨论。

如果你说的“全排列算法”是指图灵机要输出一个串的全排列（在纸带上留下全排列并停机），那么显然这不会是NP，因为光是存储全排列就需要用n!的复杂度。
至于你说的那个NTM，你大概意思也许是通过分支来生成全排列。但用NTM来考虑这个问题的时候并不方便，因为NTM的"输出"功能似乎没定义，而确定性图灵机的输出可以简单定义为停机时纸带留下的东西（并且这样的定义还是比较普遍的，不少书上也是如此定义）。

如果你说的是“检测某个串是不是某个串的排列”，这似乎只需要比较长度和字符种类与个数就可以了。

1、“全排列算法”的输入时一个串，输出什么？
2、“全排列算法”是判断性还是计算性？

搞清楚这个，大概就有答案了吧。