关于nSudoku的NP完全性假设及相关命题正确性的技术问询

先快速回顾下NP完全问题的核心定义：一个问题是NP完全的，必须满足两个条件：

• 它属于NP类：给定一个候选解，能在多项式时间内验证这个解是否正确；
• 它是NP-hard：所有NP类问题都能在多项式时间内归约到它。

我们的前提是nSudoku是NP完全问题，现在用这个来分析两个命题：

命题1：若nSudoku可多项式归约到factorization问题，则factorization是NP完全 #

咱们按逻辑链一步步推：

• 第一步：因为nSudoku是NP完全的，所以它是NP-hard的——所有NP问题都能多项式归约到nSudoku（这是NP-hard的定义）。
• 第二步：题目说nSudoku能多项式归约到factorization问题。归约是有传递性的：如果问题A能归约到B，B能归约到C，那A就能归约到C。所以这里所有NP问题都能通过nSudoku作为中间环节，最终多项式归约到factorization。
• 第三步：确认factorization属于NP类：给定一个整数N和一组候选因子，我们只需要在多项式时间内计算这些因子的乘积，验证是否等于N就行，完全符合NP的定义。
• 最后，factorization同时满足NP完全的两个条件：属于NP，且所有NP问题都能归约到它，所以它是NP完全问题。

命题2：若nSudoku可多项式归约到整数数组排序问题，则P = NP #

这个命题的关键在于利用P类问题的封闭性，思路如下：

• 第一步：整数数组排序问题是P类问题——比如归并排序、快速排序的时间复杂度都是O(n log n)，属于多项式时间范畴，所以排序问题在P里。
• 第二步：还是那个前提，nSudoku是NP完全的，所以所有NP问题都能多项式归约到nSudoku。
• 第三步：现在nSudoku能归约到排序问题，那所有NP问题都能通过这条归约链，最终多项式归约到一个P类问题。换句话说，任何NP问题都可以先转换成nSudoku实例，再转换成排序问题实例，用多项式时间的排序算法解决后，再转换回原问题的解——整个过程的总时间复杂度是多项式的（因为每一步都是多项式时间）。
• 这就意味着所有NP问题都能在多项式时间内解决，而这正是P=NP的定义。

内容的提问来源于stack exchange，提问作者proteinovij