The concepts of NP, P, and Co-NP problems were always confusing. Even during the engineering studies, after referring the most famous "fat" book "Design and Analysis of Algorithms" amble times the idea will not be impregnated in the mind. While reading the book, at one point of the peak all the concepts will clash at last we will have the condition that Co-NP is P? or will NP become P? etc. When I went to the ACE engineering academy eminent professors made me clear what exactly is happening between the P, NP, Co-NP. The ideas are sharing here.
Before thinking of the NP, P, Co-NP we must be aware of the basic facts about the deterministic and non deterministic algorithms, Decision problems, Optimization problems, Reducibility, Polynomial-Equivalence properties etc.
The great division of problems
Basically computer science problems are broadly classified into two categories.
Deterministic algorithms are again divided into polynomial time and exponential time algorithms.Polynomial time algorithms are the ones that can be solved in polynomial time complexity(O(n), O(n^2) etc). Exponential time algorithms are the ones that can be solved in exponential time complexity.(2^n, 3^n etc).
Non-deterministic algorithms are also divided in the same fashion as that of deterministic algorithms.
Why the problems are categorised into NP, NP-Hard, NP-complete, P?
The basic essence in the classification of the problems is that to show that the various problems in Computer Science are related. So in future if any scientist or researcher found out that a particular problem belong to any of these categories he can also prove that the other related problems are also belongs to the same category.
Non deterministic algorithms : First tool for the Analysis.
Every decidable problems have a non-deterministic algorithms. Determinism reveals that output is distinct. Non determinism shows that there can be more than one output for the input. Non deterministic algorithm have basically two steps. Success and failure. Success signal is generated when the algorithm is successfully completed. Its complexity is O(1). Similarly failure is the signal generated when the algorithm fails. The interesting fact of these nondeterministic algorithms is that they are theoretical.
An example for the non-deterministic algorithm for searching.
procedure nd_search(A[], n, x)
{
j = choice(i,n);
if(A[j]==x)
{
write[j];
success();
}
else
failure();
}
The above algorithm is a search algorithm which uses only O(1) time for its execution and it will returns the index of the searched element in the array of size n. The explanation is like this: The above algorithm has a function called choice(1,n). The main job of this function is that it will returns the index of the searched element with O(1) complexity.!!! Naturally we may rise the question, How this is possible, even the fastest searching deterministic algorithm will takes at least log n complexity? The answer to this question is very interesting. If a system have to return the index of the searched element atonce, that element have to be compared with every other element in the array at once. It can be done by using sufficient number of processors which compares the searched element with consecutive elements in the array parallely. If this can be done then it is possible to return the index of the searched element in O(1) time complexity. But this method is not practical. To arrange as much as processors as that of the array size is tedious and immaterial. So it is not possible. But our focus is on the nondeterministic algorithm. Thus every decidable problems have a nondeterministic algorithm. And it will be much faster than the deterministic one.
Decision Vs Optimization problems in computer science.
Any problem which has an output either YES (TRUE)or NO(FALSE) is known as decision problem. Finding an optimal value for the criteria described in the problem ( It can be either minimum or maximum) belongs to the Optimisation problems. Every decision and optimization problems are interchangeable. Some of the examples of decision problems are N-Queens, Hamiltonian Cycle problem (Does there exists a cycle connecting all the vertices's exactly once) etc. The examples of Optimization problems include 0/1 Knapsack problem(minimum weight and maximum profit), Travelling sales man problem, Graph colouring problem ( minimum number of colours needed to mark all the vertices's differently.) etc. Interesting fact about these type of problems is that they can be converted to either of each other. The examples include the conversion of 0/1 knapsack optimisation problem into 0/1 knapsack decision problem by looking the problem in another way. Is it possible to get filled up the knapsack to get maximum profit? the answer will be yes or no. Similarly, Is it possible to color a graph say with four adjacent vertices with two colours? NO, with three colours? NO, with four colours? YES. In computer science there are many standard problems that can be interchangeable between these two extremities. Some of them are max- clique, Satisfiability problem, Node cover problem etc.
Before thinking of the NP, P, Co-NP we must be aware of the basic facts about the deterministic and non deterministic algorithms, Decision problems, Optimization problems, Reducibility, Polynomial-Equivalence properties etc.
The great division of problems
Basically computer science problems are broadly classified into two categories.
- Decidable problems
- Undecidable problems
Deterministic algorithms are again divided into polynomial time and exponential time algorithms.Polynomial time algorithms are the ones that can be solved in polynomial time complexity(O(n), O(n^2) etc). Exponential time algorithms are the ones that can be solved in exponential time complexity.(2^n, 3^n etc).
Non-deterministic algorithms are also divided in the same fashion as that of deterministic algorithms.
Why the problems are categorised into NP, NP-Hard, NP-complete, P?
The basic essence in the classification of the problems is that to show that the various problems in Computer Science are related. So in future if any scientist or researcher found out that a particular problem belong to any of these categories he can also prove that the other related problems are also belongs to the same category.
Non deterministic algorithms : First tool for the Analysis.
Every decidable problems have a non-deterministic algorithms. Determinism reveals that output is distinct. Non determinism shows that there can be more than one output for the input. Non deterministic algorithm have basically two steps. Success and failure. Success signal is generated when the algorithm is successfully completed. Its complexity is O(1). Similarly failure is the signal generated when the algorithm fails. The interesting fact of these nondeterministic algorithms is that they are theoretical.
An example for the non-deterministic algorithm for searching.
procedure nd_search(A[], n, x)
{
j = choice(i,n);
if(A[j]==x)
{
write[j];
success();
}
else
failure();
}
The above algorithm is a search algorithm which uses only O(1) time for its execution and it will returns the index of the searched element in the array of size n. The explanation is like this: The above algorithm has a function called choice(1,n). The main job of this function is that it will returns the index of the searched element with O(1) complexity.!!! Naturally we may rise the question, How this is possible, even the fastest searching deterministic algorithm will takes at least log n complexity? The answer to this question is very interesting. If a system have to return the index of the searched element atonce, that element have to be compared with every other element in the array at once. It can be done by using sufficient number of processors which compares the searched element with consecutive elements in the array parallely. If this can be done then it is possible to return the index of the searched element in O(1) time complexity. But this method is not practical. To arrange as much as processors as that of the array size is tedious and immaterial. So it is not possible. But our focus is on the nondeterministic algorithm. Thus every decidable problems have a nondeterministic algorithm. And it will be much faster than the deterministic one.
Decision Vs Optimization problems in computer science.
Any problem which has an output either YES (TRUE)or NO(FALSE) is known as decision problem. Finding an optimal value for the criteria described in the problem ( It can be either minimum or maximum) belongs to the Optimisation problems. Every decision and optimization problems are interchangeable. Some of the examples of decision problems are N-Queens, Hamiltonian Cycle problem (Does there exists a cycle connecting all the vertices's exactly once) etc. The examples of Optimization problems include 0/1 Knapsack problem(minimum weight and maximum profit), Travelling sales man problem, Graph colouring problem ( minimum number of colours needed to mark all the vertices's differently.) etc. Interesting fact about these type of problems is that they can be converted to either of each other. The examples include the conversion of 0/1 knapsack optimisation problem into 0/1 knapsack decision problem by looking the problem in another way. Is it possible to get filled up the knapsack to get maximum profit? the answer will be yes or no. Similarly, Is it possible to color a graph say with four adjacent vertices with two colours? NO, with three colours? NO, with four colours? YES. In computer science there are many standard problems that can be interchangeable between these two extremities. Some of them are max- clique, Satisfiability problem, Node cover problem etc.
