Loading...
Loading...

Go to the content (press return)

2-D Tucker is PPA complete

Author
Aisenberg, J.; Bonet, M.; Buss, S.
Type of activity
Journal article
Journal
Journal of computer and system sciences
Date of publication
2020-03
Volume
108
First page
92
Last page
103
DOI
10.1016/j.jcss.2019.09.002
Project funding
Theory and applications in satisfiability and constraint optimization
Repository
http://hdl.handle.net/2117/177608 Open in new window
URL
https://www.sciencedirect.com/science/article/pii/S0022000019300674 Open in new window
Abstract
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. 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.
Citation
Aisenberg, J.; Bonet, M.; Buss, S. 2-D Tucker is PPA complete. "Journal of computer and system sciences", Març 2020, vol. 108, p. 92-103.
Keywords
NP search problems, PPA, Parity principle, TFNP, Tucker lemma

Participants