2-D Tucker is PPA complete

Inicio | ¿Qué es? | Contacto

English | Català

Consultar RECERCAT

Por comunidades y
colecciones Por fecha Por autores Por títulos Por temas (CDU)

Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Estadisticas

Del documento Todo RECERCAT

Mi RECERCAT

Entrar Alertas por correo-e

Directorio de otros repositorios

RECERCAT Principal > Universitat Politècnica de Catalunya > Documents de recerca > Visualizar documento

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: 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

Mostrar el registro sencillo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Short proofs of the Kneser-Lovász coloring principle

Aisenberg, James; Bonet Carbonell, M. Luisa; Buss, Sam; Craciun, Adrian; Istrate, Gabriel

Quasipolynomial size frege proofs of Frankl's Theorem on the trace of sets

Aisenberg, James; Bonet Carbonell, M. Luisa; Buss, Sam

Efficiently calculating evolutionary tree measures using SAT

Bonet Carbonell, M. Luisa; John, Katherine St.

Improving WPM2 for (weighted) partial MaxSAT

Ansótegui Gil, Carlos; Bonet Carbonell, M. Luisa; Gabàs, Joel; Levy Díaz, Jordi

Community structure in industrial SAT instances

Ansótegui Gil, Carlos; Bonet Carbonell, M. Luisa; Giráldez Crú, Jesús; Levy Díaz, Jordi; Simon, Laurent

Accesibilidad | Aviso legal | Política de Cookies | Documentos de uso interno

Coordinación

Patrocinio