A Formal Proof of Borodin-Trakhtenbrot’s Gap Theorem

DOI10.1007/978-3-319-03545-1_11zbMath1426.68094OpenAlexW136503236MaRDI 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

Mechanization of proofs and logical operations (03B35) Foundations of classical theories (including reverse mathematics) (03B30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formalization of mathematics in connection with theorem provers (68V20) Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)

Related Items (2)

Reverse complexity ⋮ A formalization of multi-tape Turing machines

Uses Software

• Matita

This page was built for publication: A Formal Proof of Borodin-Trakhtenbrot’s Gap Theorem