TFNP: an update

DOI10.1007/978-3-319-57586-5_1zbMATH Open1486.68080OpenAlexW2607335953MaRDI QIDQ5283350FDOQ5283350

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

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

Mathematics Subject Classification ID

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

Cites Work

• The complexity of computing a Nash equilibrium
• PRIMES is in P
• How easy is local search?
• On the complexity of the parity argument and other inefficient proofs of existence
• Settling the complexity of computing two-player Nash equilibria
• On total functions, existence theorems and computational complexity
• Title not available (Why is that?)
• Combinatorial nullstellensatz modulo prime powers and the parity argument
• Tight bounds for randomized and quantum local search
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• Integer factoring and modular square roots
• Implicit proofs
• Towards a unified complexity theory of total functions
• Title not available (Why is that?)
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• The NP Search Problems of Frege and Extended Frege Proofs
• The Journey from NP to TFNP Hardness

Cited In (3)

• Broyden updating, the good and the bad!
• The complexity of the parity argument with potential
• 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)