TFNP: An Update

DOI10.1007/978-3-319-57586-5_1zbMath1486.68080OpenAlexW2607335953MaRDI QIDQ5283350

Paul W. Goldberg, Christos H. 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)

Related Items (2)

The complexity of the parity argument with potential ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorial nullstellensatz modulo prime powers and the parity argument
• On total functions, existence theorems and computational complexity
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• Integer factoring and modular square roots
• How easy is local search?
• On the complexity of the parity argument and other inefficient proofs of existence
• Towards a unified complexity theory of total functions
• PRIMES is in P
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• Settling the complexity of computing two-player Nash equilibria
• Tight Bounds for Randomized and Quantum Local Search
• The Journey from NP to TFNP Hardness
• The Complexity of Computing a Nash Equilibrium
• The NP Search Problems of Frege and Extended Frege Proofs
• Implicit proofs

This page was built for publication: TFNP: An Update