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
Paul Goldberg, Christos Papadimitriou

#### Towards a Unified Complexity Theory of Total Functions

Revisions: 1

The complexity class TFNP is the set of {\em total function} problems that belong to NP: every input has at least one output and outputs are easy to check for validity, but it may be hard to find an output. TFNP is not believed to have complete problems, but it ... more >>>

ISSN 1433-8092 | Imprint