746
edits
add info
(add info) |
(add info) |
||
| Line 95: | Line 95: | ||
According to [[Peter J. Denning|Peter Denning]], the fundamental question underlying computer science is, "What can be automated?"<ref name="Denning_cs_discipline">{{cite journal | last=Denning | first=Peter J. | author-link=Peter J. Denning | year=2000 | title=Computer Science: The Discipline | url=http://www.idi.ntnu.no/emner/dif8916/denning.pdf | journal=Encyclopedia of Computer Science |archive-url = https://web.archive.org/web/20060525195404/http://www.idi.ntnu.no/emner/dif8916/denning.pdf |archive-date = May 25, 2006}}</ref> 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 multitude of computational problems. | According to [[Peter J. Denning|Peter Denning]], the fundamental question underlying computer science is, "What can be automated?"<ref name="Denning_cs_discipline">{{cite journal | last=Denning | first=Peter J. | author-link=Peter J. Denning | year=2000 | title=Computer Science: The Discipline | url=http://www.idi.ntnu.no/emner/dif8916/denning.pdf | journal=Encyclopedia of Computer Science |archive-url = https://web.archive.org/web/20060525195404/http://www.idi.ntnu.no/emner/dif8916/denning.pdf |archive-date = May 25, 2006}}</ref> 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 multitude of computational problems. | ||
The famous [[P versus NP problem|P = NP?]] problem, one of the [[Millennium Prize Problems]],<ref>[http://www.claymath.org/millennium/P_vs_NP/ Clay Mathematics Institute] P = NP {{webarchive |url=https://web.archive.org/web/20131014194456/http://www.claymath.org/millennium/P_vs_NP/ |date=October 14, 2013 }}</ref> is an open problem in the theory of computation. | |||