TFNP: an update

DOI10.1007/978-3-319-57586-5_1MaRDI QIDQ5283350zbMATH OpenOpenAlexFDO

Authors Paul W. Goldberg, Christos Papadimitriou

Publication date 21 July 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-57586-5_1

Mathematics Subject Classification ID

Noncooperative games (91A10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The journey from NP to TFNP hardness
• The complexity of computing a Nash equilibrium
• Towards a unified complexity theory of total functions
• On total functions, existence theorems and computational complexity
• The complexity of computing a Nash equilibrium

Cites work

• scientific article; zbMATH DE number 1263206 (Why is no real title available?)
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• Combinatorial nullstellensatz modulo prime powers and the parity argument
• How easy is local search?
• Implicit proofs
• Integer factoring and modular square roots
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• PRIMES is in P
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• Settling the complexity of computing two-player Nash equilibria
• The NP search problems of Frege and extended Frege proofs
• The complexity of computing a Nash equilibrium
• The journey from NP to TFNP hardness
• Tight bounds for randomized and quantum local search
• Towards a unified complexity theory of total functions

Cited in

(5)

• The complexity of the parity argument with potential
• The journey from NP to TFNP hardness
• Towards a unified complexity theory of total functions
• Broyden updating, the good and the bad!
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

This page was built for publication: TFNP: an update

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