In recursion theory one considers functions which can be computed by an algorithm. Computational complexity theory is dedicated to the study of the difficulty of computations based on the notion of a measure of computational complexity in terms of the amount of some resources a program uses in a specific computation. An important measure of the complexity of a computable function is the rime needed to compute it. Other resources. such as space, have also been considered.
by William I. Gasarch and Georgia A. Martin
All articles published by Studies in Informatics and Control (SIC) are published in accordance with the terms and conditions of the Creative Commons Attribution License (CC BY-NC-SA 4.0).