A Sperner lemma complete for PPA

DOI10.1016/S0020-0190(00)00152-6zbMath0996.68082WikidataQ125059452 ScholiaQ125059452MaRDI QIDQ1603412

Michelangelo Grigni

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

formal languagestheory of computation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Consensus-Halving: Does It Ever Get Easier?, 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, Unnamed Item, Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem, On the complexity of 2D discrete fixed point problem, Two's company, three's a crowd: consensus-halving for a constant number of agents, Oriented Euler complexes and signed perfect matchings, The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

Cites Work

• Unnamed Item
• On total functions, existence theorems and computational complexity
• How easy is local search?
• The relative complexity of NP search problems
• On the complexity of the parity argument and other inefficient proofs of existence