2-D Tucker is PPA complete

作者：

Highlights：

•

摘要

The 2-D Tucker search problem is shown to be PPA-hard under many-one reductions; therefore it is complete for PPA. The same holds for k-D Tucker for all k≥2. This corrects a claim in the literature that the Tucker search problem is in PPAD.

论文关键词：Tucker lemma,NP search problems,Parity principle,PPA,TFNP

论文评审过程：Received 2 January 2016, Revised 26 August 2019, Accepted 21 September 2019, Available online 26 September 2019, Version of Record 14 November 2019.

论文官网地址：https://doi.org/10.1016/j.jcss.2019.09.002