2-D Tucker is PPA complete

DOI10.1016/j.jcss.2019.09.002zbMath1436.68127OpenAlexW2976501052WikidataQ127200367 ScholiaQ127200367MaRDI QIDQ2009648

Maria Luisa Bonet, Samuel R. Buss, James Aisenberg

Publication date: 29 November 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2019.09.002

zbMATH Keywords

Tucker lemmaTFNPPPANP search problemsparity principle

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

Consensus-Halving: Does It Ever Get Easier? ⋮ Unnamed Item ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ The Hairy Ball problem is PPAD-complete ⋮ Unnamed Item ⋮ The complexity of the parity argument with potential ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ The complexity of finding fair independent sets in cycles ⋮ Two's company, three's a crowd: consensus-halving for a constant number of agents ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

Cites Work

• Integer factoring and modular square roots
• On the complexity of 2D discrete fixed point problem
• A constructive proof of Tucker's combinatorial lemma
• The relative complexity of NP search problems
• On the complexity of the parity argument and other inefficient proofs of existence
• A Sperner lemma complete for PPA
• Generalized Kneser coloring theorems with combinatorial proofs
• Short proofs of the Kneser-Lovász coloring principle
• A combinatorical proof of Kneser's conjecture
• Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
• The complexity of computing a Nash equilibrium
• Variable Dimension Complexes Part I: Basic Theory
• Variable Dimension Complexes Part II: A Unified Approach to Some Combinatorial Lemmas in Topology
• Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
• Settling the complexity of computing two-player Nash equilibria
• On the Complexity of 2D Discrete Fixed Point Problem
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Consensus halving is PPA-complete
• Understanding PPA-completeness
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler

This page was built for publication: 2-D Tucker is PPA complete