Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
From MaRDI portal
Publication:3434572
DOI10.1007/11758471_36zbMath1183.68306OpenAlexW1506563562MaRDI QIDQ3434572
Gábor Ivanyos, Yves F. Verhoeven, Katalin Friedl, Miklos Santha
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
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On the black-box complexity of Sperner's Lemma, Understanding PPA-completeness, Computing exact solutions of consensus halving and the Borsuk-Ulam theorem, 2-D Tucker is PPA complete, Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem, On the complexity of 2D discrete fixed point problem