Table of Contents
III. Theory and Mathematical Background – 40%
A. Algorithms and complexity
4. Computational complexity, including NP-completeness
a. Definition: Computability refers to whether or not a certain type of machine can solve a certain problem.
b. Definition: NP-complete problems are special problems in modern computing. The name comes from the fact that you can use a Nondeterministic Polynomial-time Turing machine to solve these problems.
c. If any problem can be solved in polynomial time, then it is part of the class P. All CFL are in P. The complement of a P language is also in P.
d. If a problem is not known to be solvable in polynomial time, but can be verified in polynomial time, then we say it is in class NP. We say NP because we know how to make nondeterministic polynomial time Turing machines to represent the problems.
e. There exist problems in NP that all other NP problems are reducible to. We say that these problems are NP-complete. Classic NP-complete problems include:
i. The Hamiltonian path problem (does a directed graph have a path that travels each node exactly once?)
ii. Composites (is a number a composite?)
iii. Clique (does a graph have a clique of a given size?)
iv. Subset-sum (given a set of numbers and target number, does the set have a subset that will add up to the target?)
v. Satisfiabilty (is a given Boolean expression satisfiable?)
vi. Vertex cover (given a graph, is there a set of k nodes that all edges touch?)
f. The compliment of an NP language is in coNP. We do not know much about this group of languages; it is not obvious if they are different from NP.
g. Other problems are not known to be in NP, but that all NP are polynomial time reducible to. We say these problems are NP-hard.
