Lifting lower bounds for tree-like proofs

DOI10.1007/s00037-013-0064-xzbMath1341.03087MaRDI QIDQ475337

J. Herrera, Sumit K. Garg

Publication date: 26 November 2014

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-013-0064-x

zbMATH Keywords

computational complexity; proof complexity

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03F20: Complexity of proofs