Theory of Computation

1.A decision problem is one that can be posed so that its answer can be written as either yes or no, e.g. whether a number is even or not. - Wikipedia

2.A decision problem is decidable if a decision algorithim exists for it. A decision algorithim is one that calculates the truth value for each input case of a decision problem, and halts for all inputs in a finite number of steps. - NIST, Decidability

3. The class P (polynomial) contains all decision problems that can be solved by a determinsitc Turing machine using a polynomial amount of time. The class NP (non-determinsitic polynomial time) is the collection of problems whose solutions can be verified in a polynomial amount of time - Complexity Classes, MIT News

4. The P vs NP problem asks whether a problem that can be quickly verified can also be quickly solved. Michael Sipser, the head of the MIT Department of Mathematics and a member of the Computer Science and Artificial Intelligence Lab’s Theory of Computation Group (TOC), says that the P-versus-NP problem is important for deepening our understanding of computational complexity - MIT News

5.$1,000,000 richer