| Popis: |
Turing's beautiful capture of the concept of computability by the “Turing machine” linked computability to a device with explicit steps of operations and use of resources. This invention led in a most natural way to build the foundations for computational complexity. §1. Introduction . Computational complexity provides mechanisms for classifying combinatorial problems and measuring the computational resources necessary to solve them. The discipline provides explanations of why no practical solutions to certain problems have been found, and provides a way of anticipating difficulties involved in solving these problems. The classification is quantitative and is intended to investigate what resources are necessary, lower bounds, and what resources are sufficient, upper bounds, to solve various problems. This classification should not depend on a particular computational model but rather should measure the intrinsic difficulty of a problem. Precisely for this reason, as we will explain, the basic model of computation for our study is the multitape Turing machine. Computational complexity theory today addresses issues of contemporary concern, for example, parallel computation, circuit design, computations that depend on random number generators, and development of efficient algorithms. Above all, computational complexity is interested in distinguishing problems that are efficiently computable. Algorithms whose running times are n 2 in the size of their inputs can be implemented to execute efficiently even for fairly large values of n , but algorithms that require an exponential running time can be executed only for small values of n . |
