On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence

On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence, by C.H. Papadimitriou

定义了几个新的搜索问题的复杂性类,处于FP和FNP之间。这些新的类和factoring及PLS类一起均在FNP中的总有一个witness的搜索问题的TFNP类中。在这些新的类中的一个问题,用一个隐藏给出的,指数级大的图的方式定义。而找到的解的存在性是由一个简单的图论的有非有效的构造性证明得出的结论建立起来的。例如PLS可以被对应于图论中的“每个dag拥有一个sink”的事实。新的类则是基于“每个图拥有偶数个奇度定点”这样的事实。它们包含一些重要的问题,这些问题没有目前已知的多项式时间的算法,包含Sperner引理,Brouwer不动点定理,Chevalley定理的计算版本和Borsuk-Ulam定义,P-矩阵线性补问题,寻找一个非零和博弈的混合均衡,在一个Hamilton cubic图中寻找一个第二Hamilton回路,在quartic图中寻找一个第二Hamilton分解等。其中一些被证明是完全的。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s