Towards a unified complexity theory of total functions

DOI10.1016/j.jcss.2017.12.003zbMath1393.68053OpenAlexW2776865190MaRDI QIDQ1745728

Christos H. Papadimitriou, Paul W. Goldberg

Publication date: 18 April 2018

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8340/

zbMATH Keywords

computational complexityfirst-order logicPLSproof systemPPPTFNPPPAPPADNP search functionsPPADS

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items

The NP Search Problems of Frege and Extended Frege Proofs, TFNP: An Update, Approximate counting and NP search problems, Total functions in QMA, The Hairy Ball problem is PPAD-complete, The classes PPA-\(k\): existence from arguments modulo \(k\), The classes PPA-\(k\): existence from arguments modulo \(k\), The complexity of the parity argument with potential, The Hairy Ball Problem is PPAD-Complete., Characterising the intersection of QMA and coQMA, The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Propositional proofs and reductions between NP search problems
• The provably total NP search problems of weak second order bounded arithmetic
• 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
• 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
• A complexity gap for tree resolution
• Quasipolynomial size proofs of the propositional pigeonhole principle
• The provably total search problems of bounded arithmetic
• Approximate counting by hashing in bounded arithmetic
• Settling the complexity of computing two-player Nash equilibria
• Quantified propositional calculi and fragments of bounded arithmetic
• 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
• Provability of the pigeonhole principle and the existence of infinitely many primes
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• The Complexity of Computing a Nash Equilibrium
• Consensus halving is PPA-complete
• The NP Search Problems of Frege and Extended Frege Proofs
• NP search problems in low fragments of bounded arithmetic
• Implicit proofs
• Propositional representation of arithmetic proofs (Preliminary Version)
• Improved witnessing and local improvement principles for second-order bounded arithmetic
• Automata, Languages and Programming
• CONSISTENCY OF CIRCUIT EVALUATION, EXTENDED RESOLUTION AND TOTAL NP SEARCH PROBLEMS