Halting Problem

停机问题和理发师悖论有一点相似，结论是不存在一个程序可以判定自身是否存在死循环。

Turning Machine | 图灵机

:::info

• 确定性图灵机（Deterministic Turing Machine）：每一个状态只能执行一条指令，状态转移也只能由一个点到另外一个点。

• 非确定性图灵机（Nondeterministic Turing Machine）：可以同时转移到多个状态，总是可以选择正确的一步。 ::: :::danger

• 即使对于非确定性图灵机，不可计算问题仍为不可计算问题。 :::

  P, NP, NPC, NP-Hard

  Overview

  :::info

• P 表示可以由确定性图灵机在多项式时间内解决的问题。

• NP 表示可以由非确定性图灵机在多项式时间内解决的问题。
  • 等价于确定性图灵机在多项式时间内能验证

• 悬而未决的问题是 P=NP or P != NP

  • 若 P=NP，则 NP 问题都有多项式时间解法
  • 若 P !=NP，则存在 NP 问题没有多项式时间解法 ::: 首先提出一个概念——问题的归约，如下图所示：
    :::info

• NPC：所有 NP 问题都可以归约到的问题称为 NP 完全问题

  • 所有 NPC 问题在难度上等价，解决其中一个也就意味着解决了所有 NPC，也解决了所有的 NP 问题
  • 要证明一个问题是 NPC
    1. 问题是 NP 的
    2. 一个已知的 NPC 问题 该问题
• NP-Hard：一个已知的 NPC 问题该问题（NP-Hard 不一定是 NP 问题） ::: 下面是一张关系图：
  

  Circuit-SAT

  第一个被证明是 NPC 的问题。
  

  3-SAT

TSP | Traveling Salesman Problem

哈密顿回路问题已被证明是 NPC 的，我们只要证明 TSP 可以归约到哈密顿回路问题即可。

Formal Language Theory | 形式化语言