Classifying computational problems according to their inherent difficulty, and relating those classes to each other. A problem is inherently difficult if its solution requires significant resources.
An infinite collection of instances together with a solution for every instance.
A special type of computational problem whose answer is typically yes or no
Example: The input is an arbitrary graph. The problem consists in deciding whether the graph is connected or not. The formal language associated with the problem is the set of all connected graphs. In this case, graphs must be encoded in some form of a string.
A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape.
All programming languages can be computed with a Turing machine. Any computer is Turing complete if it can compute anything a Turing machine can.
A deterministic Turing machine is the most basic machine. It uses a fixed set of rules to determine its future actions. Being deterministic, it will always evaluate to the same outcome.
A non-deterministic Turing machine is a deterministic Turing machine with non-determinism, allowing it to have multiple possible future actions for a state. It can branch into many possible computational paths at each step. Not realistically feasible, but an interesting postulate for complexity classes.
A set of problems of related resource-based complexity. A class is the set of problems solved by abstract machine M using O(f(n)) of resource R, where n is the size of the input.
P (Polynomial) is the class of problems with polynomial algorithms.
The complexity class NP (Non-deterministic Polynomial) is the set of problems with no known efficient algorithm. P is a subset of, and possibly equal to NP.
A reduction is a transformation of one problem into another problem. Captures the informal notion of a problem being at least as difficult as another problem.
Hardness for a complexity class says that form a hard problem X in complexity class C, all problems in C can be reduced to X. The set of problems for NP is called NP-hard.
If a problem X in C is hard for C, then X is said to be complete for C. NP-complete contains the hardest problems in NP, that are least likely to be in P.