2-D Tucker is PPA complete

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/177608

Title:	2-D Tucker is PPA complete
Author:	Aisenberg, James; Bonet Carbonell, M. Luisa; Buss, Sam
Other authors:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
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.
Abstract:	Peer Reviewed
Subject(s):	-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat -Computational complexity -Tucker lemma -NP search problems -Parity principle -PPA -TFNP -Complexitat computacional
Rights:	Attribution-NonCommercial-NoDerivatives 4.0 International ©2019. Elsevier https://creativecommons.org/licenses/by-nc-nd/4.0/
Document type:	Article - Submitted version Article
Share: