Publication:5465358

zbMath1079.03050MaRDI QIDQ5465358

Samuel R. Buss

Publication date: 22 August 2005

zbMATH Keywords

fragments of bounded arithmetic; Paris-Wilkie translation; bounded depth Frege systems; PK-proof systems

Mathematics Subject Classification ID

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

03F05: Cut-elimination and normal-form theorems

03F30: First-order arithmetic and fragments

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

03F20: Complexity of proofs