Further collapses in TFNP

DOI10.1137/22M1498346MaRDI QIDQ6543098zbMATH OpenFDO

Authors Mika Göös, Alexandros Hollender, Siddhartha Jain, William Pires, Robert Robere, Ran Tao

Publication date 24 May 2024

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/22M1498346

zbMATH Keywords

\textsf{EOPL}\textsf{PLS}\textsf{PPAD}\textsf{TFNP}

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites work

• Adventures in monotone complexity and TFNP
• ARRIVAL: a zero-player graph game in \(\text{NP}\cap \text{coNP}\)
• ARRIVAL: next stop in CLS
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• How easy is local search?
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Tarski's theorem, supermodular games, and the complexity of equilibria
• The complexity of computing a Nash equilibrium
• The complexity of gradient descent: CLS = PPAD ∩ PLS
• The complexity of sharing a pizza
• The complexity of the parity argument with potential
• The Hairy Ball problem is PPAD-complete
• The rainbow at the end of the line -- a \textsf{PPAD} formulation of the colorful Carathéodory theorem with applications
• The relative complexity of NP search problems
• Unique end of potential line

Cited in

(2)

• Reducing Tarski to unique Tarski (in the black-box model)
• Settling the complexity of Nash equilibrium in congestion games

This page was built for publication: Further collapses in \(\mathsf{TFNP}\)

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