Intersection classes in TFNP and proof complexity

DOI10.4230/LIPICS.ITCS.2024.74MaRDI QIDQ6906353zbMATH OpenFDO

Authors Yu-Hao Li, William Pires, Robert Robere

Publication date 4 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2024.74

zbMATH Keywords

intersection classesproof complexityTFNP

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Adventures in monotone complexity and TFNP
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Colourful TFNP and propositional proofs
• Constant rank two-player games are PPAD-hard
• Further collapses in TFNP
• How easy is local search?
• scientific article; zbMATH DE number 1114017 (Why is no real title available?)
• scientific article; zbMATH DE number 7561747 (Why is no real title available?)
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Lower bounds for resolution and cutting plane proofs and monotone computations
• On reducibility and symmetry of disjoint NP pairs.
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• On the complexity of Nash equilibria in anonymous games
• On the complexity of the parity argument and other inefficient proofs of existence
• On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
• Propositional proofs and reductions between NP search problems
• Semialgebraic Proofs and Efficient Algorithm Design
• Separations in proof complexity and TFNP
• Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
• Settling the complexity of computing two-player Nash equilibria
• Simple Local Search Problems that are Hard to Solve
• TFNP characterizations of proof systems and monotone circuits
• The complexity of computing a Nash equilibrium
• The complexity of equilibria: Hardness results for economies via a correspondence with games
• The complexity of gradient descent: CLS = PPAD pls
• The Complexity of Non-Monotone Markets
• The complexity of the parity argument with potential
• The relative complexity of NP search problems
• Unique end of potential line

Cited in

(2)

• TFNP intersections through the Lens of feasible disjunction
• Separations in proof complexity and TFNP

This page was built for publication: Intersection classes in TFNP and proof complexity

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