End of Potential Line
End of Potential Line
复制标题
电位线末端
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Rahul Savani
中科院分区：
文献类型：
--
作者：
John Fearnley;Spencer Gordon;R. Mehta;Rahul Savani
我们介绍了所有问题的问题和相应的复杂性类EOPL，这些问题可以在多项式时间内降低到它。该课程捕获了一种问题，这些问题可以接受其在复杂性课程中的共同成员资格的单一组合证明，即FIXPOINT问题和本地搜索问题的PLS。 EOPL是类CLS类的组合定义的替代方案（用于连续的本地搜索），其目的是捕获PPAD $ \ CAP $ PLS中一些众所周知的问题的复杂性，在某些情况下，它抗拒了抵抗几十年来，试图将它们置于多项式时间。其中两个是收缩，这是找到收缩图的固定点和p-lcp的问题，即解决P-Matrix线性互补问题的问题。
我们表明，通过将双向电池降低到Endofemeteredline，Endofpotentialline在CLS中。后者被定义为显示CLS的查询和密码下限。我们的两个主要结果是表明PL-contraction（分段线性收缩）和P-LCP都在EOPL中。我们的降低意味着PL-Contraction和P-LCP的承诺版本在Promise Class UliqueeOpl中，这与单个电势线的情况相对应。这也表明，简单，折扣，平均付款和平等游戏在EOPL中。
利用我们减少的PL-Contaction的见解，我们获得了第一种多项式时间算法，用于在任何$ \ ell_p $ norm中找到固定尺寸的固定点的收缩点，以前此类算法仅对$ \ ell_2 $知道和$ \ ell_ \ infty $ norms。我们从P-LCP到EndofatientLine的还原允许应用Aldous技术，这又为P-LCP提供了最快的随机算法。
We introduce the problem EndOfPotentialLine and the corresponding complexity class EOPL of all problems that can be reduced to it in polynomial time. This class captures problems that admit a single combinatorial proof of their joint membership in the complexity classes PPAD of fixpoint problems and PLS of local search problems. EOPL is a combinatorially-defined alternative to the class CLS (for Continuous Local Search), which was introduced in with the goal of capturing the complexity of some well-known problems in PPAD $\cap$ PLS that have resisted, in some cases for decades, attempts to put them in polynomial time. Two of these are Contraction, the problem of finding a fixpoint of a contraction map, and P-LCP, the problem of solving a P-matrix Linear Complementarity Problem.
We show that EndOfPotentialLine is in CLS via a two-way reduction to EndOfMeteredLine. The latter was defined in to show query and cryptographic lower bounds for CLS. Our two main results are to show that both PL-Contraction (Piecewise-Linear Contraction) and P-LCP are in EOPL. Our reductions imply that the promise versions of PL-Contraction and P-LCP are in the promise class UniqueEOPL, which corresponds to the case of a single potential line. This also shows that simple-stochastic, discounted, mean-payoff, and parity games are in EOPL.
Using the insights from our reduction for PL-Contraction, we obtain the first polynomial-time algorithms for finding fixed points of contraction maps in fixed dimension for any $\ell_p$ norm, where previously such algorithms were only known for the $\ell_2$ and $\ell_\infty$ norms. Our reduction from P-LCP to EndOfPotentialLine allows a technique of Aldous to be applied, which in turn gives the fastest-known randomized algorithm for the P-LCP.
DOI：
10.1007/s10009-019-00509-3
发表时间：
2019-06-01
影响因子：
1.5
作者：
Fearnley, John;Jain, Sanjay;Wojtczak, Dominik
通讯作者：
Wojtczak, Dominik
线尾的彩虹 - 彩色卡拉西奥多里定理的 PPAD 公式及其应用
DOI：
10.1137/1.9781611974782.87
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
Meunier;Frédéric;Mulzer;Wolfgang;Sarrabezolles;Pauline;Yannik
通讯作者：
Yannik