Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes

DOI10.1007/11758471_36MaRDI QIDQ3434572zbMATH OpenOpenAlexFDO

Authors Katalin Friedl, Gábor Ivanyos, Miklos Santha, Yves F. Verhoeven

Publication date 2 May 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11758471_36

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35)

Recommendations

• A Sperner lemma complete for PPA
• On the Complexity of 2D Discrete Fixed Point Problem
• On the complexity of 2D discrete fixed point problem
• \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
• Understanding PPA-completeness

Cited in

(6)

• On the complexity of 2D discrete fixed point problem
• 2-D Tucker is PPA complete
• Understanding PPA-completeness
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• On the black-box complexity of Sperner's Lemma

This page was built for publication: Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3434572)