2-D Tucker is PPA complete

DOI10.1016/J.JCSS.2019.09.002MaRDI QIDQ2009648zbMATH OpenOpenAlexWikidataFDO

Authors James Aisenberg, Maria Luisa Bonet, Samuel R. Buss

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

NP search problemsparity principlePPATFNPTucker lemma

Mathematics Subject Classification ID

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

Recommendations

• Complete solution to the \(TP_{2}\) completion problem
• Understanding PPA-completeness
• Understanding PPA-completeness
• scientific article; zbMATH DE number 1004241
• A further improvement on approximating TTP-2
• Consensus halving is PPA-complete
• scientific article; zbMATH DE number 1140626
• Projection 2 Goes Turbulent - and Fully Implicit

Cites work

• A combinatorical proof of Kneser's conjecture
• A constructive proof of Tucker's combinatorial lemma
• A Sperner lemma complete for PPA
• Consensus halving is PPA-complete
• Generalized Kneser coloring theorems with combinatorial proofs
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Integer factoring and modular square roots
• Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
• On the complexity of 2D discrete fixed point problem
• On the Complexity of 2D Discrete Fixed Point Problem
• On the complexity of the parity argument and other inefficient proofs of existence
• Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
• Settling the complexity of computing two-player Nash equilibria
• Short proofs of the Kneser-Lovász coloring principle
• The complexity of computing a Nash equilibrium
• The relative complexity of NP search problems
• 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
• Variable Dimension Complexes Part I: Basic Theory
• Variable Dimension Complexes Part II: A Unified Approach to Some Combinatorial Lemmas in Topology

Cited in

(15)

• The complexity of the parity argument with potential
• The complexity of finding fair independent sets in cycles
• Two's company, three's a crowd: consensus-halving for a constant number of agents
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• The Hairy Ball problem is PPAD-complete
• Hardness results for consensus-halving
• scientific article; zbMATH DE number 7561747 (Why is no real title available?)
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• Consensus-Halving: Does It Ever Get Easier?
• Computational complexity of the -Ham-Sandwich problem
• Computing a fixed point of contraction maps in polynomial queries
• Constant inapproximability for PPA
• The complexity of finding fair independent sets in cycles
• Strong approximate consensus halving and the Borsuk-Ulam theorem

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

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