Towards a Unified Complexity Theory of Total Functions

DOI10.4230/LIPIcs.ITCS.2018.37zbMath1462.68062OpenAlexW2783207967MaRDI QIDQ4993302

Paul W. Goldberg, Christos H. Papadimitriou

Publication date: 15 June 2021

Full work available at URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.37

zbMATH Keywords

computational complexityfirst-order logicproof systemTFNPNP search functions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Propositional proofs and reductions between NP search problems
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• Integer factoring and modular square roots
• Complexity classes without machines: on complete languages for UP
• On the complexity of polyhedral separability
• The relative complexity of NP search problems
• On the complexity of the parity argument and other inefficient proofs of existence
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• Quasipolynomial size proofs of the propositional pigeonhole principle
• Approximate counting by hashing in bounded arithmetic
• Settling the complexity of computing two-player Nash equilibria
• Polynomial size proofs of the propositional pigeonhole principle
• A method for obtaining digital signatures and public-key cryptosystems
• The relative efficiency of propositional proof systems
• 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: Towards a Unified Complexity Theory of Total Functions