Reverse complexity

DOI10.1007/S10817-015-9349-XMaRDI QIDQ287279zbMATH OpenOpenAlexFDO

Authors 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

hierarchy theoremsinteractive theorem provingmachine-independent complexityreverse complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Reversal Complexity
• Reversal complexity revisited
• Structural analysis of the complexity of inverse functions
• GENERALIZED COUNTERS AND REVERSAL COMPLEXITY
• Theory and Applications of Models of Computation
• scientific article; zbMATH DE number 4007730
• Complexity Analysis by Rewriting
• Reversibility in space-bounded computation
• Reversible programming languages capturing complexity classes
• The complexity of reversible cellular automata

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 3438370 (Why is no real title available?)
• scientific article; zbMATH DE number 1531925 (Why is no real title available?)
• scientific article; zbMATH DE number 7106484 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A Web Interface for Matita
• A formal proof of Borodin-Trakhtenbrot's gap theorem
• A formalization of multi-tape Turing machines
• A new recursion-theoretic characterization of the polytime functions
• Automated Reasoning
• Bounded arithmetic for NC, ALogTIME, L and NL
• Classes of computable functions defined by bounds on computation
• Computational Complexity
• Computational Complexity and the Existence of Complexity Gaps
• Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
• Formalizing Turing Machines
• Guest editorial: Special issue on implicit computational complexity
• Logical foundations of proof complexity
• Matita Tutorial
• Mechanising Turing machines and computability theory in Isabelle/HOL
• On the Computational Complexity of Algorithms
• Recursive Properties of Abstract Complexity Classes
• Subsystems of second order arithmetic
• The Matita interactive theorem prover
• The intensional content of Rice's theorem
• Toward a Theory of Enumerations

Cited in

(3)

• scientific article; zbMATH DE number 5595793 (Why is no real title available?)
• Reverse formalism 16
• A formal proof of Borodin-Trakhtenbrot's gap theorem

Describes a project that uses

Uses Software

• Matita
• Isabelle/HOL

This page was built for publication: Reverse complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q287279)