A tight Karp-Lipton collapse result in bounded arithmetic

DOI10.1145/1805950.1805952zbMath1351.03055OpenAlexW1989692246WikidataQ59903238 ScholiaQ59903238MaRDI QIDQ2946610

Sebastian Müller, Olaf Beyersdorff

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1805950.1805952

zbMATH Keywords

bounded arithmeticadviceKarp-Lipton theoremoptimal propositional proof systemsextended Frege

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items

Proof systems that take advice ⋮ Do there exist complete sets for promise classes?