P, NP, and NP-Complete Problems

P, NP, and NP-Complete Problems

In Computer Science, many problems objective is to maximize or minimize some values, whereas in other problems objective is to find whether there is a solution or not. Hence, the problems can be categorized as follows −

Optimization Problem:

Optimization problems are those for which the objective is to maximize or minimize some values. For example,

•    Finding the minimum number of colors needed to color a given graph.

•    Finding the shortest path between two vertices in a graph.

Decision Problem:

These are problems for which the answer is a Yes or a No. These types of problems are known as decision problems. For example,

•    Whether a given graph can be colored by only 4-colors.

In the study of the computational complexity of problems, the first concern of both computer scientists and computing professionals is whether a given problem can be solved in polynomial time by some algorithm.

An algorithm is said to solve a problem in polynomial time if its worst-case time efficiency belongs to O(p(n)) where p(n) is a polynomial of the problem’s input size n.

Problems that can be solved in polynomial time are called tractable, and problems that cannot be solved in polynomial time are called intractable.

Some decision problems cannot be solved at all by any algorithm. Such problems are called undecidable, as opposed to decidable problems that can be solved by an algorithm.

P Problems

Class P is a class of decision problems that can be solved in polynomial time by (deterministic) algorithms. This class of problems is called polynomial.

Informally, problems that can be solved in polynomial time are the set called as P. A more formal definition includes in P only decision problems, which are problems with yes/no answers.

NP Problems

Class NP is the class of decision problems that can be solved by nondeterministic polynomial algorithms. This class of problems is called nondeterministic polynomial.

Every problem in this class can be solved in exponential time using exhaustive search. These are problems that are decidable but intractable.

A nondeterministic algorithm is a two-stage procedure that takes as its input an instance I of a decision problem and does the following:

•          Nondeterministic (“guessing”) stage: An arbitrary string S is generated that can be thought of as a candidate solution to the given instance I.
•          Deterministic (“verification”) stage: A deterministic algorithm takes both I and S as its input and outputs yes if S represents a solution to instance I. (If S is not a solution to instance I, the algorithm either returns no or is allowed not to halt at all.)

A nondeterministic algorithm is said to be nondeterministic polynomial if the time efficiency of its verification stage is polynomial. Most decision problems are in NP.

P versus NP:

, 

if a problem is in P, the deterministic polynomial time algorithm that solves it can be used in the verification-stage of a nondeterministic algorithm that simply ignores string S generated in its nondeterministic (“guessing”) stage.

NP-Complete Problems:

A decision problem D is said to be NP-complete if:

1. It belongs to class NP

2. Every problem in NP is polynomial time reducible to D.

A problem is NP-Hard if it follows property 2 mentioned above, doesn’t need to follow property 1. Therefore, NP-Complete set is also a subset of NP-Hard set.

The problem in NP-Hard cannot be solved in polynomial time, until P = NP. If a problem is proved to be NPC, there is no need to waste time on trying to find an efficient algorithm for it. Instead, focus on designing of an approximation algorithm for the problem.