NP 问题

停机问题

停机问题是一个经典的不可判定问题，即无法找到一个算法来判断任意程序是否会停机。停机问题的形式化定义为：给定一个程序 \(P\) 和一个输入 \(I\)，我们希望找到一个算法 \(H(P, I)\) 来判断程序 \(P\) 在输入 \(I\) 下是否会停机。

停机问题的不可判定性可以通过反证法证明：假设存在一个算法 \(H(P, I)\) 可以判断停机问题，那么我们可以构造一个新的程序 \(P'\)：

def P'(P):
    if H(P, P) == True:
        while True:
            pass
    else:
        return

然后我们调用 \(H(P', P')\)，如果 \(P'\) 会停机，\(P'\) 就不会停机，反之亦然，这就产生了矛盾。

图灵机

图灵机由一个无限长的纸带和一个读写头组成，纸带上划分了无限多个格子，读写头包含了有限的状态。在每个时刻，读写头可以读取当前格子上的符号，并根据当前状态和读取的符号执行一系列操作：改变当前格子上的符号、移动读写头、改变当前状态。

确定型图灵机 (Deterministic Turing Machine, DTM) 是一种特殊的图灵机，它在任何时刻都只有一个可能的操作。非确定型图灵机 (Non-deterministic Turing Machine, NTM) 则可以在某些时刻有多个可能的操作，如果这些操作中有一个可以达到目标状态，那么 NTM 就会选择这个操作。

NP 问题的定义

NP (Nondeterministic polynomial-time) 问题是一类问题的集合，其中每个问题的解可以在多项式时间内验证，或者可以在多项式时间内被非确定型图灵机解决。P 问题则是可以在多项式时间内解决的问题的集合，显然 P 问题是 NP 问题的子集。

NPC (NP-complete) 问题是一类 NP 问题的集合，其中每个 NP 问题都可以在多项式时间内归约到 NPC 问题。如果我们能够找到一个多项式时间的算法来解决任何一个 NPC 问题，那么我们就可以在多项式时间内解决所有 NP 问题，因为任何 NP 问题都可以归约到 NPC 问题。