The complexity of the parity argument with potential

DOI10.1016/j.jcss.2021.03.004OpenAlexW3136449553MaRDI QIDQ2037189

Takashi Ishizuka

Publication date: 30 June 2021

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.2021.03.004

zbMATH Keywords

computational complexityPLSsearch problemsPPAEOPL

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• On total functions, existence theorems and computational complexity
• 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
• 2-D Tucker is PPA complete
• Communication complexity of approximate Nash equilibria
• Unique end of potential line
• Zero-Sum Polymatrix Games: A Generalization of Minmax
• Settling the complexity of computing two-player Nash equilibria
• The complexity of pure Nash equilibria
• Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
• The Hairy Ball Problem is PPAD-Complete.
• The Complexity of Computing a Nash Equilibrium
• The complexity of splitting necklaces and bisecting ham sandwiches
• A converse to Banach's fixed point theorem and its CLS-completeness
• Consensus halving is PPA-complete
• TFNP: An Update

This page was built for publication: The complexity of the parity argument with potential