Friday, July 10, 2009

Theory of computation

The study of the theory of computation is focused on answering fundamental questions about what can be computed, and what amount of resources are required to perform those computations. In an effort to answer the first question, computability theory examines which computational problems are solvable on various theoretical models of computation. The second question is addressed by computational complexity theory, which studies the time and space costs associated with different approaches to solving a computational problem.

The famous "P=NP?" problem, one of the Millennium Prize Problems,[19] is an open problem in the theory of computation.

P = NP ?
Computability theory Computational complexity theory


No comments:

Post a Comment