【理论学习】FP、FNP、TFNP、PPA、PPAD定义简记

本文简单记录及其前置的几个复杂性类的定义。

Decision Problem

决定性问题。图灵机不是有两个特殊格局Accept和Reject吗，如果问题是这种“YES or NO”的问题，最后由这两个特殊格局提供答案，那就是Decision Problem。

一个Decision Problem可以记为某一字母表上的关系：

Function Problem

Function Problem的输出为字符串，Decision Problem可以粗略地认为是它的子集。

一个Function Problem可以记为某一字母表上的关系：

FP

对于一个Function Problem，如果存在一个确定型图灵机在多项式时间内输出其答案，则该问题为问题。

FNP

对于一个Function Problem，如果存在一个确定型图灵机在多项式时间内验证其答案（或等价地，存在一个非确定型图灵机在多项式时间内输出其答案），则该问题为问题。

TFNP

wiki：

A binary relation P(x,y) is in TFNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(x,y) holds given both x and y, and for every x, there exists a y which is at most polynomially longer than x such that P(x,y) holds.

T也就是Total，指的是每一个输入都有输出。不仅如此，下输出的规模必须至多多项式级别地长于输入规模。

PPA

要理解这个复杂性类，首先要知道handshaking lemma：

对于任意无向图，若图中有一个奇度数点，则必有另一个奇度数点。

现在，已知一张无向图，表示其顶点的字符串为-bit二进制串（注意，这意味着这张图的规模可以是指数级别的），该图以多项式级别电路（事实上就是一个函数）的形式表示给算法，该电路以顶点为输入，输出其邻居。（这使得我们可以对这个指数级别的图进行高效的局部搜索）

假设图中存在一个奇度数点并已给出，请找出另一个奇度数点。

对于一个Function Problem ，当且仅当可多项式时间可规约到上述问题。

根据handshaking lemma，另一个奇度数点一定是存在的；

同时，对于该问题的一个解，很容易利用在多项式时间内检验这个解是否正确。

因此.

PPAD

也就是变成了有向图。

具体来讲，定义的问题称为End-Of-The-Line问题：

是一个可能有指数级别规模的有向图，每个顶点至多有一个前驱，且至多有一个后继。由一个多项式时间可计算的函数给出，它输出的前驱和后继。

现在，存在一个已给出的没有前驱的顶点，请找到另一个没有前驱或没有后继的顶点。

可以证明，.

Christos Papadimitriou于1994年提出了上述的和复杂性类。

假设，可以证明，严格易于。

不仅如此，即使，仍然有可能。

上述事实表明，是一类难度介于和的问题。

John Nash证明了，纳什均衡在人有限博弈中总是存在的。

因此，如果有问题是：给定某个game，求是否存在纳什均衡。那么这个问题显然是的，因为直接输出“YES”就好了。

但是，“是否存在不止一个纳什均衡”则是的。

Papadimitriou还证明了，给定收益矩阵，计算2人及以上的非零和博弈的纳什均衡是的。

这种十分自然的中介性的问题是十分难得的，所以因为这类问题的发掘，也越来越受到关注。