Everything about Implicit computational complexity
Implicit computational complexity (ICC) is a subfield of computational complexity theory that characterizes programs by constraints on the way in which they are constructed, without reference to a specific underlying machine model or to explicit bounds on computational resources unlike conventional complexity theory. The central goal of ICC is to identify programming formalisms ā such as restricted formal languages, type systems, or recursion schemes ā whose expressive power coincides exactly with a given complexity class, so that membership in the class becomes a consequence of syntactic well-formedness rather than a separate computational argument. ICC was developed in the 1990s and employs the techniques of proof theory, substructural logic, linear logic, model theory and recursion theory to prove bounds on the expressive power of high-level formal languages. Among its founding contributions are Girard, Scedrov, and Scottās bounded linear logic (1992), Bellantoni and Cookās function algebra based on predicative recursion (1992), and Jonesās cons-free programming language characterisation of polynomial time (1999). ICC is also concerned with the practical realization of functional programming languages, language tools and type theory that can control the resource usage of programs in a formally verifiable sense. Wikipedia ā
š§ Start here: a 6-step reading path
- Read the overview: Implicit computational complexityA 5-minute orientation
- Skim a recent paper: Implicit computation complexity in higher-order programming languagesInfluential work since 2022
- Pick up a classic book: Recent advances in real complexity and computationThe most-reprinted book on the subject
- Read the landmark paper: Quantum implicit computational complexityCited 24 times
- Go sideways: Primitive recursive functionA closely related topic
- Go sideways: Recursion (computer science)A closely related topic
š Definitions
No dictionary entry for this exact phrase.
šļø The subject at a glance
š Landmark papers (most cited)
Quantum implicit computational complexity
Formal security proofs with minimal fuss: Implicit computational complexity at work
Reversible computing and implicit computational complexity
Probabilistic Recursion Theory and Implicit Computational Complexity
Proceedings International Workshop on Developments in Implicit Computational complExity
Implicit Computational Complexity of Subrecursive Definitions and Applications to Cryptographic Proofs
Developments in implicit computational complexity
The Implicit Computational Complexity Flavor of Automata
š Influential since 2022
š Books worth reading
- šRecent advances in real complexity and computationSpain) UIMP-RSME Lluis SantalĆ³ Summer (2012 Santander Ā· 2013
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
š Related topics
- Primitive recursive function In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are allā¦
- Recursion (computer science) In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the sameā¦
- Decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yesāno question on aā¦
- General recursive function In mathematical logic and computer science, a general recursive function, partial recursive function, or Ī¼-recursive function is a partial function fromā¦
- Elementary function arithmetic In proof theory, a branch of mathematical logic, elementary function arithmetic (EFA), also called elementary arithmetic and exponential function arithmeticā¦
- TC0 In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC0 (Threshold Circuit) is the first class inā¦
- P (complexity) In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that canā¦
- NC (complexity) Unsolved problem in computer science ā šš¢=?šÆā More unsolved problems in computer science In computational complexity theory, the class NC (for Nick'sā¦