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

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

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

• Combinatorial nullstellensatz modulo prime powers and the parity argument
• How easy is local search?
• scientific article; zbMATH DE number 1263206 (Why is no real title available?)
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• 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 complexity of computing a Nash equilibrium
• The journey from NP to TFNP hardness
• The NP search problems of Frege and extended Frege proofs
• Tight bounds for randomized and quantum local search
• Towards a unified complexity theory of total functions

Cited in

(6)

• Towards a unified complexity theory of total functions
• Broyden updating, the good and the bad!
• The complexity of the parity argument with potential
• The journey from NP to TFNP hardness
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• An oracle with no up-complete sets, but NP = PSPACE

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)