Computer Science – Computational Complexity
Scientific paper
2009-11-27
Computer Science
Computational Complexity
26 pages, no figures
Scientific paper
It is currently not possible to quantify the resources needed to perform a computation. As a consequence, it is not possible to reliably evaluate the hardware resources needed for the application of algorithms or the running of programs. This is apparent in both computer science, for instance, in cryptanalysis, and in neuroscience, for instance, comparative neuro-anatomy. A System versus Environment game formalism is proposed based on Computability Logic that allows to define a computational work function that describes the theoretical and physical resources needed to perform any purely algorithmic computation. Within this formalism, the cost of a computation is defined as the sum of information storage over the steps of the computation. The size of the computational device, eg, the action table of a Universal Turing Machine, the number of transistors in silicon, or the number and complexity of synapses in a neural net, is explicitly included in the computational cost. The proposed cost function leads in a natural way to known computational trade-offs and can be used to estimate the computational capacity of real silicon hardware and neural nets. The theory is applied to a historical case of 56 bit DES key recovery, as an example of application to cryptanalysis. Furthermore, the relative computational capacities of human brain neurons and the C. elegans nervous system are estimated as an example of application to neural nets.
No associations
LandOfFree
Quantifying Resource Use in Computations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantifying Resource Use in Computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantifying Resource Use in Computations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-195713