Changes

[[Theoretical computer science]] is the mathematical study of what can and cannot in principle be computed under various constraints. For example, [[Alan Turing]] [[halting problem|proved]] that it is impossible to write a computer program that can determine whether other computer programs will ever ''halt'', or whether they will run forever. Other problems which can be solved in principle seem impossible to solve efficiently. For example, the famous P vs. NP problem asks whether there exists a polynomial time algorithm to solve any NP-complete problem, like the [[travelling salesman problem]]. There is a $1,000,000 prize for the solution to the P vs. NP problem.

[[Theoretical computer science]] is the mathematical study of what can and cannot in principle be computed under various constraints. For example, [[Alan Turing]] [[halting problem|proved]] that it is impossible to write a computer program that can determine whether other computer programs will ever ''halt'', or whether they will run forever. Other problems which can be solved in principle seem impossible to solve efficiently. For example, the famous P vs. NP problem asks whether there exists a polynomial time algorithm to solve any NP-complete problem, like the [[travelling salesman problem]]. There is a $1,000,000 prize for the solution to the P vs. NP problem.

[[Category:Information technology]]

[[Category:Information Technology]]

[[Category:Computer Science]]

[[Category:Computer Science]]