2-D Tucker is PPA complete

Home | About RECERCAT | Contact

Català | Castellano

All of RECERCAT

By Communities &
Collections By Defense Date By Authors By Titles By Subject

This Collection

By Defense Date By Authors By Titles By Subject

Statistics

View Statistics All RECERCAT

My RECERCAT

Other repositories directory

RECERCAT Home > Universitat Politècnica de Catalunya > Documents de recerca > View document

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

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Aisenberg, James
dc.contributor.author	Bonet Carbonell, M. Luisa
dc.contributor.author	Buss, Sam
dc.date	2020-03
dc.identifier.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.
dc.identifier.citation	0022-0000
dc.identifier.citation	10.1016/j.jcss.2019.09.002
dc.identifier.uri	http://hdl.handle.net/2117/177608
dc.language.iso	eng
dc.relation	https://www.sciencedirect.com/science/article/pii/S0022000019300674
dc.relation	info:eu-repo/grantAgreement/ES/1PE/TIN2013-48031-C4-1-P
dc.rights	Attribution-NonCommercial-NoDerivatives 4.0 International
dc.rights	©2019. Elsevier
dc.rights	https://creativecommons.org/licenses/by-nc-nd/4.0/
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
dc.subject	Computational complexity
dc.subject	Tucker lemma
dc.subject	NP search problems
dc.subject	Parity principle
dc.subject	PPA
dc.subject	TFNP
dc.subject	Complexitat computacional
dc.title	2-D Tucker is PPA complete
dc.type	info:eu-repo/semantics/submittedVersion
dc.type	info:eu-repo/semantics/article
dc.description.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.
dc.description.abstract	Peer Reviewed

Show simple item record

All of RECERCAT

This Collection

Statistics

My RECERCAT

Related documents

Other documents of the same author