COMS W3261 CS Theory
Lecture 19: The Classes P and NP

1. Time Complexity

We now turn our attention to recursive languages and ask the question "How quickly can a Turing machine determine whether a given input string w is in a given recursive language L?"
We say that a function T(n) is O(f(n)) [read "big-O of f(n)"] if there exists an integer n₀ and a constant c > 0 such that for all integers n ≥ n₀, we have T(n) ≤ cf(n).
Big-O notation allows us to ignore constant factors and just focus on asymptotic behavior. E.g., T(n) = 2n² is O(n²).
Big-O notation allows us to ignore low-order terms. E.g., T(n) = 2n² + 3n + 4 is O(n²).
A Turing machine M is of time complexity T(n) if on any input of length n, M halts after making at most T(n) moves.
Note that time complexity is a worst-case measure. If a Turing machine M is of time complexity T(n), then it makes at most T(n) moves on any input of length n.

We define P to be the set of languages L such that L = L(M) for some deterministic Turing machine M of time complexity T(n) where T(n) is a polynomial function of n.
A problem that cannot be solved in polynomial time is said to be intractable.
NP is the set of languages L such that L = L(M) for some nondeterministic Turing machine M where on any input of length n, there are no sequences of more than T(n) moves of M where T(n) is a polynomial function of n.
At present, it is not known whether all problems in NP can be solved in polynomial time. The question of whether P = NP is one of the most important open problems in computer science and mathematics.
The Clay Mathematics Institute has identified the P vs NP question as one of its seven Millennium Prize Problems and offers a one million dollar prize for its solution.

In our study of problems that can be solved in polynomial time, we restrict ourselves to polynomial-time reductions.
A polynomial-time reduction is an algorithm that maps any instance I of problem A into an instance J of problem B in a number of steps that is a polynomial function of the length of I such that I is in A iff J is in B.
Note that in a polynomial-time reduction the length of J must be a polynomial function of the length of I.

A language satisfying condition (2) is said to be NP-hard.
If A is NP-complete, B is in NP, and there is a polynomial-time reduction of A to B, then B is NP-complete.
If any one NP-complete problem is in P, then P = NP.
Examples of problems in P

Determining whether a set of integers has a nonempty subset whose sum is zero ("subset sum"). Note that we can verify a zero-sum subset in deterministic polynomial time, but finding if one exists is difficult.
Finding a cycle in a graph that contains each node exactly once ("the Hamiltonian cycle problem"). Again, note that verifying that a cycle is Hamiltonian is easy, but finding a Hamiltonian cycle is hard.
Lots of others.

Determining whether two graphs are isomorphic. Laszlo Babai of the University of Chicago has again announced he has a quasipolynomial time algorithm for graph isomorphism.
Not that many others.


E → E ∨ T | T
T → T ∧ F | F
F → ( E ) | ¬ F | var

var represents a variable whose value can be either 1 (for true) or 0 (for false).

The operator ∧ stands for logical AND, ∨ for logical OR, and ¬ for logical NOT.

Note that the grammar gives the operator ¬ the highest precedence, then ∧, then ∨.

A truth assignment for a boolean expression assigns either the value true (1) or the value false (0) to each of the variables in the expression.
The value E(T) of an expression E given a truth assignment T is the result of evaluating E with each variable x in E replaced by T(x).
A truth assignment T satisfies E if E(T) = 1.
An expression E is satisfiable if there exists a truth assignment T that satisfies E.
The satisfiability problem (SAT) is to determine whether a given boolean expression is satisfiable.

The value of E = x ∧ ¬(y ∨ z) given the truth assignment T(x) = 1, T(y) = 0, T(x) = 0 is 1. [1 ∧ ¬(0 ∨ 0) = 1]. Thus, E is satisfiable.
The expression E = x ∧ (¬x ∨ y) ∧ ¬y is not satisfiable because none of the four truth assignments to the variables x and y causes E to have the value 1.

Is the function n^{log n} polynomial or exponential, where log is to the base 2?
Show that the function 2n² is O(n²).
Show that the function 2n² + 3n + 4 is O(n²).
Show that if f(n) and g(n) are polynomial functions, then f(g(n)) is a polynomial function.
If M is a nondeterministic Turing machine of time complexity T(n), then show that M can be simulated by a deterministic Turing machine of time complexity O(2^T(n)).
Show that P and NP closed under the following operations: