Jump to content

Implicit computational complexity

Edit links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Citation bot (talk | contribs) at 21:20, 24 August 2023 (Alter: title, template type. Add: class, date, eprint, s2cid, chapter-url, chapter, authors 1-4. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 804/1947). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

  1. ^ "ICC'01 - Implicit Computational Complexity". www.dcs.ed.ac.uk. Retrieved 2023-08-06.
  2. ^ "Implicit Computational Complexity". perso.ens-lyon.fr. Retrieved 2023-08-06.
  3. ^ "No.033 Implicit Computational Complexity and Applications: Resource Control, Security, Real-Number Computation | SeminarsNII Shonan Meeting". NII Shonan Meeting. Retrieved 2023-08-06.
  4. ^ 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. pp. 1–13. arXiv:2110.01114. doi:10.1145/3531130.3533340. ISBN 978-1-4503-9351-5. S2CID 238259005.
  5. ^ "DICE 2014 – Developments in Implicit Computational Complexity". dice14.tcs.ifi.lmu.de. Retrieved 2023-08-06.
  6. ^ Aubert, Clément; Rubiano, Thomas; Rusch, Neea; Seiller, Thomas (2022). "Realizing Implicit Computational Complexity". arXiv:2203.05221 [cs.CC].
P ≟ NP 

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Implicit_computational_complexity&oldid=1172085606"