The classes PPA-k: existence from arguments modulo k

DOI10.1007/978-3-030-35389-6_16MaRDI QIDQ5896088zbMATH OpenOpenAlexFDO

Authors Alexandros Hollender

Publication date 30 June 2020

Published in Web and Internet Economics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-35389-6_16

zbMATH Keywords

computational complexitynecklace splittingTFNP

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• The classes PPA-\(k\): existence from arguments modulo \(k\)
• The complexity of splitting necklaces and bisecting ham sandwiches
• Consensus halving is PPA-complete
• A Sperner lemma complete for PPA
• On the polynomial parity argument complexity of the combinatorial Nullstellensatz

Cites work

• Consensus halving is PPA-complete
• How easy is local search?
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• Integer factoring and modular square roots
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Propositional proofs and reductions between NP search problems
• Reducibility among fractional stability problems
• Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
• Settling the complexity of computing two-player Nash equilibria
• Simplotopal maps and necklace splitting
• Splitting necklaces
• The Borsuk--Ulam-property, Tucker-property and constructive proofs in combinatorics
• The complexity of computing a Nash equilibrium
• The complexity of equilibria: Hardness results for economies via a correspondence with games
• The Complexity of Non-Monotone Markets
• The complexity of pure Nash equilibria
• The complexity of splitting necklaces and bisecting ham sandwiches
• The Hairy Ball Problem is PPAD-Complete.
• The relative complexity of NP search problems
• Towards a unified complexity theory of total functions
• Unique End of Potential Line

Cited in

(5)

• A survey of mass partitions
• scientific article; zbMATH DE number 7561747 (Why is no real title available?)
• The complexity of splitting necklaces and bisecting ham sandwiches
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• The classes PPA-\(k\): existence from arguments modulo \(k\)

This page was built for publication: The classes PPA-\(k\): existence from arguments modulo \(k\)

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