The complexity of the parity argument with potential
type: Item
instance of: scholarly article
title: The complexity of the parity argument with potential
author: Takashi Ishizuka
published in: Journal of Computer and System Sciences
publication date: 2021-06-30T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7365378
zbMATH Keywords: computational complexity
zbMATH Keywords: search problems
zbMATH Keywords: PPA
zbMATH Keywords: PLS
zbMATH Keywords: EOPL
MaRDI profile type: Publication
full work available at URL: j.jcss.2021.03.004
OpenAlex ID: W3136449553
cites work: 2-D Tucker is PPA complete
cites work: Communication complexity of approximate Nash equilibria
cites work: The relative complexity of NP search problems
cites work: Zero-sum polymatrix games: a generalization of minmax
cites work: Settling the complexity of computing two-player Nash equilibria
cites work: The Complexity of Computing a Nash Equilibrium
cites work: Q5365081
cites work: A converse to Banach's fixed point theorem and its CLS-completeness
cites work: The complexity of pure Nash equilibria
cites work: Unique end of potential line
cites work: Consensus halving is PPA-complete
cites work: The complexity of splitting necklaces and bisecting ham sandwiches
cites work: The Hairy Ball Problem is PPAD-Complete.
cites work: TFNP: An Update
cites work: Towards a unified complexity theory of total functions
cites work: Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
cites work: How easy is local search?
cites work: On total functions, existence theorems and computational complexity
cites work: On the complexity of the parity argument and other inefficient proofs of existence
DOI: 10.1016/J.JCSS.2021.03.004
description: scientific article; zbMATH DE number 7365378