Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NP SEARCH FUNCTIONS:
Reports tagged with NP Search Functions:
TR15-163 | 11th October 2015
James Aisenberg, Maria Luisa Bonet, Sam Buss

#### 2-D Tucker is PPA complete

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\ge 2$. This corrects a claim in the literature that the Tucker search problem is in PPAD.

more >>>

TR17-056 | 7th April 2017