Understanding PPA-completeness

DOI10.1016/j.jcss.2020.07.006zbMath1464.68121OpenAlexW3047060986MaRDI QIDQ2208253

Jack Edmonds, Zhe Feng, Xiaotie Deng, Zeying Xu, Qi Qi, Zhengyang Liu

Publication date: 23 October 2020

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5831/

zbMATH Keywords

fixed-point computationoracle model complexityPPA-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Triangulating manifolds (57Q15) Relations of low-dimensional topology with graph theory (57M15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Consensus-Halving: Does It Ever Get Easier? ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential lower bounds for finding Brouwer fixed points
• On the complexity of 2D discrete fixed point problem
• The computation of fixed points and applications
• Some graphic uses of an even number of odd nodes
• The complexity of finding a second Hamiltonian cycle in cubic graphs
• On the complexity of the parity argument and other inefficient proofs of existence
• A Sperner lemma complete for PPA
• Complementary pivot theory of mathematical programming
• Discrete Fixed Points: Models, Complexities, and Applications
• Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
• Settling the complexity of computing two-player Nash equilibria
• Matching algorithmic bounds for finding a Brouwer fixed point
• The complexity of promise problems with applications to public-key cryptography
• Some Combinatorial Lemmas in Topology
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Combinatorial Nullstellensatz
• Consensus halving is PPA-complete
• Constant rank bimatrix games are PPAD-hard
• Equilibrium Points of Bimatrix Games
• Hard-to-Solve Bimatrix Games
• The Approximation of Fixed Points of a Continuous Mapping
• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs

This page was built for publication: Understanding PPA-completeness