The complexity of the parity argument with potential
From MaRDI portal
Publication:2037189
DOI10.1016/j.jcss.2021.03.004OpenAlexW3136449553MaRDI QIDQ2037189
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
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