The classes PPA-\(k\): existence from arguments modulo \(k\)

DOI10.1007/978-3-030-35389-6_16zbMath1435.68107OpenAlexW2991500167MaRDI QIDQ5896088

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

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

Related Items (3)

A survey of mass partitions ⋮ Unnamed Item ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

Cites Work

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

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