ON OPTIMAL INVERTERS

DOI10.1017/bsl.2013.2zbMath1341.03052OpenAlexW2329233923MaRDI QIDQ2925321

Jörg Flum, Yijia Chen

Publication date: 21 October 2014

Published in: The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/bsl.2013.2

zbMATH Keywords

survey paper

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Complexity of proofs (03F20)

Related Items

A remark on pseudo proof systems and hard instances of the satisfiability problem ⋮ Hard Instances of Algorithms and Proof Systems

Cites Work

• Unnamed Item
• Almost every set in exponential time is P-bi-immune
• Which problems have strongly exponential complexity?
• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS
• Propositional proof systems, the consistency of first order theories and the complexity of computations