Reverse complexity

DOI10.1007/s10817-015-9349-xzbMath1356.03052OpenAlexW2913667992MaRDI QIDQ287279

Andrea Asperti

Publication date: 26 May 2016

Published in: Journal of Automated Reasoning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10817-015-9349-x

zbMATH Keywords

interactive theorem provinghierarchy theoremsmachine-independent complexityreverse complexity

Mathematics Subject Classification ID

Uses Software

• Isabelle/HOL
• Matita

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A formalization of multi-tape Turing machines
• Bounded arithmetic for NC, ALogTIME, L and NL
• A new recursion-theoretic characterization of the polytime functions
• A Web Interface for Matita
• Formalizing Turing Machines
• A Formal Proof of Borodin-Trakhtenbrot’s Gap Theorem
• The intensional content of Rice's theorem
• Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
• Matita Tutorial
• The Matita Interactive Theorem Prover
• Automated Reasoning
• Computational Complexity
• Mechanising Turing Machines and Computability Theory in Isabelle/HOL
• On the Computational Complexity of Algorithms
• Classes of computable functions defined by bounds on computation
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Toward a Theory of Enumerations
• Computational Complexity and the Existence of Complexity Gaps
• Recursive Properties of Abstract Complexity Classes
• Guest editorial

This page was built for publication: Reverse complexity