Implicit computational complexity
Implicit computational complexity (ICC) is a subfield of computational complexity theory that characterizes algorithms 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.[1][2] ICC was developed in the 1990s and employs the techniques of proof theory, substructural logic, model theory and recursion theory to prove bounds on the expressive power of high-level formal languages.[3][4] 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.[5][6]
References
- ^ "ICC'01 - Implicit Computational Complexity". www.dcs.ed.ac.uk. Retrieved 2023-08-06.
- ^ "Implicit Computational Complexity". perso.ens-lyon.fr. Retrieved 2023-08-06.
- ^ "No.033 Implicit Computational Complexity and Applications: Resource Control, Security, Real-Number Computation | SeminarsNII Shonan Meeting". NII Shonan Meeting. Retrieved 2023-08-06.
- ^ Curzi, Gianluca; Das, Anupam (2022-08-04). "Cyclic Implicit Complexity". Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS '22. New York, NY, USA: Association for Computing Machinery: 1–13. doi:10.1145/3531130.3533340. ISBN 978-1-4503-9351-5.
- ^ "DICE 2014 – Developments in Implicit Computational Complexity". dice14.tcs.ifi.lmu.de. Retrieved 2023-08-06.
- ^ "Realizing Implicit Computational Complexity".