A Formal Proof of Borodin-Trakhtenbrot’s Gap Theorem

DOI10.1007/978-3-319-03545-1_11zbMath1426.68094MaRDI QIDQ2938046

Andrea Asperti

Publication date: 13 January 2015

Published in: Certified Programs and Proofs (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-03545-1_11

zbMATH Keywords

reverse complexity

Mathematics Subject Classification ID

03B35: Mechanization of proofs and logical operations

03B30: Foundations of classical theories (including reverse mathematics)

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

68V20: Formalization of mathematics in connection with theorem provers

68V15: Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.)

Related Items

Reverse complexity, A formalization of multi-tape Turing machines

Uses Software

• Matita