On the computational complexity of finding hard tautologies

DOI10.1112/BLMS/BDT071zbMath1345.03107arXiv1212.1789OpenAlexW2106792056MaRDI QIDQ5402611

Jan Krajíček

Publication date: 14 March 2014

Published in: Bulletin of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1212.1789

zbMATH Keywords

propositional proof systemsproof complexityNisan-Wigderson generator

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (1)

ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS

This page was built for publication: On the computational complexity of finding hard tautologies