# Complexity Of Problems

The Class P

The class of decision problems P consists of those decision problems whose yes/no solution can be obtained using a deterministic algorithm that runs in polynomial number of steps, i.e., in O (nk) steps, for some nonnegative integer k, where n is the input size.

sorting: Given a list of n integers, are they sorted in nondecreasing order?

set disjointness: Given two sets of integers, is their intersection empty?

shortest path: Given a directed graph G = (V;E) with positive weights on its edges, two distinguished vertices and a positive integer k, is there a path from s to t whose length is at most k?

2-coloring: Given an undirected graph G, is it 2-colorable?, i.e., can its vertices be colored using only 2 colors such that no two adjacent vertices are assigned the same color? Note that G is 2-colorable if and only if it is bipartite, that is, if and only if it does not contain cycles of odd length.

We say that a class of problems C is closed under complementation if for any problem  the complement of  is also in C. For instance, the complement of the 2-colorable? Let us call this problem NOT-2-COLOR. We can show that it is in P as follows. Since 2-COLORING is in P, there is a determinsitic algorithm A which when presented with a 2-colorable graph halts and answers yes, and when presented with a graph that is not 2-colorable halts and answers no. We can simply design a determinsitic algorithm for the problem NOT-2-COLOR by simply interchanging the yes and no answers in Algorithm A.

This, informally, proves the following fundamental theorem :

Theorem 10.1 The class P is closed under complementation.

The Class NP

The class NP consists of those problems
π for which there exists a deterministic algorithm A which, when presented with a claimed solution to an instance of π, will be able to verify its correctness in polynomial time. That is, if the claimed solution leads to a yes answer, there is a way to verify this solution in polynomial time. In order to define this class less informally, we must first define the concept of a nondeterministic algorithm. On input x, a nondeterministic algorithm consists of two phases

(a) The guessing phase : In this phase, an arbitrary string of characters y is generated. It may correspond to a solution to the input instance or not. In fact, it may not even be in the proper format of the desired solution. It may differ from one run to another of the nondeterministic algorithm.

(b) The verification phase : In this phase, a deterministic algorithm defines two things. First, it checks whether the generated solution string y is in the proper format. If it is not, then the algorithm halts with the answer no. If, on the other hand, y is in the proper format, then the algorithm continues to check whether it is a solution to the instance x of the problem. If it is indeed a solution to the instance x, then it halts and answers yes; otherwise it halts and answers no.

# NP-complete Problems

The term NP-complete” denotes the subclass of decision problems in NP that are hardest in the sense that if one of them is proven to be solvable by a polynomial time deterministic algorithm, then all problems in NP are solvable by a polynomial time deterministic algorithm, i.e., NP = P. For proving that a problem is NP-complete, we need the following definition.

• Definition Let Π and Π′ be two decision problems. We say that Π reduces to Π′ in polynomial time, symbolized as , if there exists a determinsitic algorithm A that behaves as follows. When A is presented with an instance I of problem Π, it transforms it into an instance I′ of problem Π′ such that the answer to I is yes if and only if the answer to I′ is yes. Moreover, this transformation must be achieved in polynomial time.
• Definition A decision problem Π is said to be NP-hard if for every problem Π′ in NP, .
• Definition A decision problems Π is said to be NP-complete if
(1) Π is in NP, and
(2) for every problem Π′ in NP, .
Thus, the difference between an NP-complete problem Π and an NP-hard problem Π′ is that Π must be in the class NP whereas Π′ may not be in NP.