2-D Tucker is PPA complete
From MaRDI portal
Publication:2009648
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
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
