In this lecture, we classify problems by their complexity.
Decision problems have yes or no answers.
Mathematicians like to simplify analysis, so they consider only decision problems. Nevertheless many problems can be reduced to a decision problem.
All existence problems are decision problems, for example does the graph has a cycle is a decision problem.
Many construction problems are related to decision problems by asking if a potential solution of the problem is in fact a solution. The potential solution to the problem is part of the input to the problem.
If that if there are only polynomial solutions and each solution can be generated in polynomial time then the related decision problem can solve the construction problem in polynomial time by generating and checking each potential solution.
Class P is a class of all decision problems that can be solved in polynomial time by deterministic algorithms.
Deterministic algorithms are the algorithms that do not guess at a solution.
An interesting question is, are there any decision problem that is not in P? In fact there is a problem that can have a solution, for example the Halting problem.
The halting problem is there a program that can determine if any program will halt on an input or continue running for ever.
Turing showed that there is no such program in 1936.
Proof
Proof by contraction. Assume there is such a program, A, which takes another program, P, and an input I and returns
A(P, I) = 1, if Program P halts on input I
A(P, I) = 0, if program P does not halt on input I
We construct another program which uses the program as input
Q(P) halts, if A(P, P) = 0, i.e. P does not halt on input P
Q(P) does not halt, if A(P, P) = 1, i.e. P does halt on input P
Now input Q into Q
Q(Q) halts if A(Q, Q) = 0, i.e. Q does not halt on input Q
Q(Q) does not halt, if A(Q, Q) = 1, i.e. Q does halt on input Q
Note both outputs of Q are contradictions.
There are many decidable problems which do not have polynomial time solutions.
Hamiltonian circuit: Does a graph have a Hamiltonian circuit, a circuit that visit each node only once?
Traveling salesman decision problem: Does a weight graph have Hamiltonian circuit with length N?
Knapsack Problem decision problem: Can the knapsack be loaded with items valued at V?
Bin packing decision problem: Can n rational numbers (all less than 1) be put into M bins size 1?
Graph coloring decision problem: Can a graph be colored with N different color so that no two colored vertices are adjacent.
Note that for all these problems a potential solution can be checked in polynomial time.
An informal definition for a nondeterministic algorithm is an algorithm that can guess at the solution (nondeterministic step) but checks that the solution is correct using a deterministic algorithm.
Class NP is the class of all decision problems that a nondeterministic algorithm can solve in polynomial time.
Note P is a subset of NP
We do not know if P is equal to NP.
The informal definition of NP-complete (NPC) problem is NP problem that is as difficult as any other problem in NP.
A decision problem D1 is polynomially reducible to another decision problem D2 if there exist a function t that transform instances of D1 to instances of D2 such that
1. t maps all yes/no instances of D1 to yes/no instances of D2
2. t is polynomial time
A decision problem, D, is NP complete if
1. It belongs to NP
2. Every problem in NP is polynomial reducible to D
Part 1 in the definition is generally trivial to demonstrate, but part 2 of the definition can be very difficult.
Generally scientist show that a know NPC decision problem is polynomial reducible to the problem. This required someone to demonstrate the first NPC problem.
Stephen Cook in 1971 showed that the CNF-satisfiability problem is NPC. Since then all the other decision problem mention above have been shown to NPC.