In Computer Science, many problems are solved where the objective is to maximize or minimize some values, whereas in other problems we try 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

There are many 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.

• Finding Hamiltonian cycle in a graph is not a decision problem, whereas checking a graph is Hamiltonian or not is a decision problem.

What is Language?

Every decision problem can have only two answers, yes or no. Hence, a decision problem may belong to a language if it provides an answer ‘yes’ for a specific input. A language is the totality of inputs for which the answer is Yes. Most of the algorithms discussed in the previous chapters are polynomial time algorithms. For input size n, if worst-case time complexity of an algorithm is O(n k ), where k is a constant, the algorithm is a polynomial time algorithm..

In this context, we can categorize the problems as follows −

P-Class

The class P consists of those problems that are solvable in polynomial time, i.e. these problems can be solved in time O(n k ) in worst-case, where k is constant. These problems are called tractable, while others are called intractable or superpolynomial.

NP-Class

The class NP consists of those problems that are verifiable in polynomial time. NP is the class of decision problems for which it is easy to check the correctness of a claimed answer, with the aid of a little extra information. Hence, we aren’t asking for a way to find a solution, but only to verify that an alleged solution really is correct.

Every problem in this class can be solved in exponential time using exhaustive search.

NP-Complete Problems

Following are some NP-Complete problems, for which no polynomial time algorithm is known.

• Determining whether a graph has a Hamiltonian cycle

• Determining whether a Boolean formula is satisfiable, etc

  NP-Hard Problems

The following problems are NP-Hard

• The circuit-satisfiability problem

• Set Cover

• Vertex Cover

• Travelling Salesman Problem, In this context, now we will discuss TSP is NP-Complete