# Computation Complexity

## Computation Difficulty: P, EXP, R

```
P     = {problems solvable in polynomial time}
EXP   = {problems solvable in exponential time}
R     = {problems solvable in finite time}
```

这里，polynomial time 指 $$O(n^c)$$ ，exponential time 指 $$O(2^{n^c})$$ ，其中 c 为常数。

它们之间的关系如图 1 所示：

![图 1 - Computation Complexity](/files/-LRj4e408Y4G-LuLtuoe)

## P, NP, NP-Hard, NP-Complete

### P 问题

许多问题都属于 P，如我们耳熟能详的排序算法、最短路径算法等。

### NP 问题

在理解 NP 问题之前，需要引入一个概念：Decision Problems。它是指答案为是或否的问题，它的解决方案通常由一个个小决定串联而成。如俄罗斯方块（Tetris），每一种方案都由无数个小形状如何放置的决定串联而成。我们可以将所有问题都抽象成这种形式，于是可以通过两种角度来理解 NP 问题的定义：

1. 假如在解决一个问题的每一个决定中，我们都能够幸运地猜中最佳选项，这个问题能在 polynomial 的时间内被解决。
2. 虽然我们无法找到一个确定的方案能在 polynomial 的时间内解决该问题，但我们确定能在 polynomial 的时间内检查一个方案是否正确。

#### NP 问题举例：

* 俄罗斯方块

#### P 与 NP

在计算复杂度理论领域，有一个推论：

$$
P \neq NP
$$

它的引申含义可以有：

1. 我们无法把运气编写到程序中
2. 找到一个解决方案比验证一个解决方案难

这个推论至今未被证明。因此图 1 中，NP 与 P 之间的空白是否真的存在，还未有定论。

#### NP-Hard

NP-Hard 问题指的是难度大于或等于所有 NP 问题的问题。如 EXP、R 问题等。

#### NP-Complete

$$
NPComplete = NP \cap NPHard
$$

NP-Complete 问题位于 NP 与 NP-Hard 的交集点上。

NP-Complete 问题举例：

* Knapsack
* 3-Partition: given n integers, can you divide them into triples of equal sum?
* Traveling Salesman Problem
* Longest Common Sbusequence of K Strings
* Minesweeper, Sudoku & most puzzles
* SAT: given a Boolean formula (and, or, not), is it ever true?
* shortest paths in 3D
* 3-coloring a given graph
* find largest clique in a given graph

## EXP/EXP-Hard/EXP-Complete

与 NP/NP-Hard/NP-Complete 之间的关系类似。Chess 是一个 EXP-Complete 问题。

## Uncomputable Problem

### Halting Problem

*输入任意一个计算机程序，它运行一段时间后会停顿吗？*目前没有任何算法能够在有限时间内解决该问题，因此它不在 R 的范围内。

### Most Decision Problems Are Uncomputable

尽管在计算机理论与实践过程中，我们遇到的大部分问题都是在有限时间内可以解决的，但实际上大部分 Decision Problems 都无法在有限时间内解决。

#### 证明

* Decision Problem 可以被抽象成寻找这样一个函数：输入是某个字符串（二进制序列），即问题描述；输出为是或否，即问题的答案。而这个字符串可以是任意字符串，因此它可以被进一步抽象成一个实数。
* Program 被转换成机器码以后就是一段有限长度的二进制序列，因此它可以被进一步抽象成一个整数。
* 由于实数的数量远远多于整数，因此大部分 Decision Problems 都无法在有限时间内计算得到结果。

证明完毕

## Reductions

将新问题转化成熟悉的问题的技术。举例如下：

* unweighted shortest path => weighted (set weights = 1)
* min-product path => shortest path (take logs)
* longest path => shortest path (negate weights)
* shortest ordered tour => shortest path (k copies of the graph)
* cheapest leaky-tank path => shortest path (graph reduction)

Reduction 又分为 One-call reductions 和 Multi-call reductions，主要区别在于将新问题转化为一个还是多个熟悉的问题。

所有的 NP-Complete 问题都可以互相转化，因此它们的难度一样。所有 NP-Complete 问题的共同祖先是 3-Partition 问题。

## 参考：

[6.006 course notes](https://courses.csail.mit.edu/6.006/fall11/notes.shtml)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/mit-6.006/computation-complexity.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.