I will explain complexity classes then its type and their interrelation with each other with examples for making it easy to understand. Then we will see how we can give algorithm to prove this problem or solve this problem. By support of some examples we will see how they are equal and are not equal. Officially this problem statement was given by Stephen cook.
We all know about complexity classes in computer science and there is always a question which is either P=NP or not. This problem is one from millennium prize problem[1] of computer science announced by Clay Mathematics Institute in 2000.when someone will give the correct algorithm for such problem they will award them with US $ 10,00,000. We all know that all P problems are in NP but if someone could prove that if all NP problems in P then we can say that P=NP.
I have explaining this topic because it is quite interesting to learn about an open question in computer science where so many problems are getting faster solutions but some of them are still as they were before in history of computer science.
Introduction:
In Computer Science, there are so many problems for some we have solutions and for some we don’t have solutions. Complexity class deals with these type of problems. These types of problems are divided into classes which are called Complexity Class.
The Scott Aaronson said
“If P=NP then the world would be profoundly different place than we usually assume it to be. There would be no special values in ‘creative leaps’, no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart. Everyone who could follow a step by step argument would be a Gauss…” [2]
In Theory of Computation we studies the resources which are required to solve such type of problems. Its resources are similar to algorithms that is time and memory. How much time does it take to solve any given problem and how much memory does it take to solve problems.
Origin:
Stephen Arthur Cook (1939) is an American computer scientist who gave a great contribution to the complexity theory and its proof. He is considered as a forefathers of computer complexity theory. He published his research work in 1971 and made an example of Boolean satisfiability to prove the existence of NP complete problem in the computer science world. This research paper also generated a question or formulated that whether P and NP problems that is if some question can be verified in P, polynomial time or optimal time, then there is also an algorithm which can solve this question or verified problem in optimal way. But there are so many problems for which we can be verified easily but cannot be solved easily.
Complexity:
The complexity classes means whenever we increases the input size the growth function and required resources also increases so complexity problems are related with resources.
The formal definition of complexity classes is “The set of problems that can be solved by an abstract machine M using O (f (n)) of resource R, where n is the size of the input.”[3]
It does not deals with seconds and bytes as complexity of programming problems do in computer science. The same type of problems is grouped together and put in a class to see as a same kind of problems.
The resources used while solving a particular class of problem can be either time or number of operations performed by machine on each step to get required output. So many complexity classes are defined by their mode of computation that is one based on
⦁ By Modal of Computation: These type of problems based on deterministic [4] and non-deterministic Turing machines [5].
⦁ Based On Type of Computation: such type of problems generally related to decision problems.
⦁ Resources based problems which have its own complexity class of problems of same type.
⦁ Based On Reduction: There are so many complexity classes based on reductions. Reduction helps in transforming one problem to another. Like we have A problem which is from NP class and the problem statement which is toughest we guess can be transformed to known problem that is A to solve easily to get the answer is method of reduction. There are so many problems in computer science for which first we convert them to easier class for which the solution is known then we apply optimal algorithm to get the solution in easiest way.
The problem as an example if we want to calculate the square of any number then it can be easily converted to multiplication problem or reduced to multiplication problem to apply the optimal algorithm to get the best solution. From above classification we have taken some complexity classes to make a classification of known problems of same type.
There are several complexity classes and some of them are subset or superset of others.
⦁ P Class
⦁ NP Class
⦁ Co- NP Class
⦁ NP Hard Class
⦁ NP Complete Class
Before discussing Millennium Prize Problem, I am going to explain brief description about each class.
⦁ P Complexity Class: (P : Deterministic Polynomial Time)
In complexity theory P is also known as PTIME and it is fundamental complexity class. This class contains all problems which can be solved in polynomial amount of time by deterministic Turing machine. And it is independent complexity class because whenever we write an algorithm to solve any program and call a function which takes polynomial amount of time then the time complexity of algorithm becomes polynomial hence it goes under the P class.
All problems which takes polynomial amount of time falls under this class and the problem of such class is easy to verify and solve.
A Graphical Relation which will show you how they are related. https://en.wikipedia.org/wiki/P_versus_NP_problem#/media/File:P_np_np-complete_np-hard.svg
⦁ NP Class: (Non-Deterministic Polynomial Time)
In complexity theory NP is most fundamental complexity class which is super class of NP hard and NP complete problems and complement of Co-NP problems. In this class the decision problems accepts “yes” in polynomial amount of time by non-deterministic Turing Machine.
A graphical representation of NP Class.
For this type of problem, they are easy to verify but it is hard to find their solution.
Example: Let us we have 1000 of people and 100 of rooms in a hotel and we want to allocate a room to pair of 10 peoples. I put some restrictions there, I gave a list of people to the manager of hotel and told him not to allow these people to stay in same room if they are change their rooms. As we know in decision problem after allocating the room it is easy to verify by the manager from the list if he finds any pair of people not according to that list he will say No that they have not paired according to that list and when he will swap their room and after checking from the list, he will say Yes now they are according to that list. So if we want to make an algorithm to allocate the room so there are larger number of possible of pairings which will not be easy to hotel manager so such type of problems falls under this NP Class category which is easy to verify but hard to get the solution.
Co- NP class is opposite of NP class problems that is if answer to any problem is no in Co-NP class then yes will be answer from NP class.
The NP Hard Class problems are those problems which NP reduces to it. All NP hard problems are not in NP Class because when we give any solution to NP Hard Problems then it is not easy to verify the solution of that problem. Let us take an example if we have a problem Z which is NP Hard Problem and if any polynomial time algorithm exists for this NP Hard Problem then polynomial time algorithm for every problem is NP.
So If Z is NP Hard Problem implies that it can be solved in polynomial time then we can say that P=NP that both class of complexity, P and NP are equal.
Now NP complete complexity class where problem is part of both classes that is NP hard and NP itself. So if someone finds polynomial time algorithm for NP complete problem then we can easily find polynomial time algorithm for every NP complete problems. Which will help in checking answer faster.
NP hard problems are impossible to solve and in general. The set of problems which are in NP are easier than their toughest problem.
Now We have discussed what is complexity classes and type of complexity classes and Now we will check whether P problems are equals to NP problems that is when someone find a polynomial time algorithm for NP problems then they becomes equal.
Problem Based On P and NP Class:
Example 1.
Tower of Hanoi Problem
In this Tower of Hanoi problem we have to move all disk from one rod to another rod based on some condition but in this steps we have to check or verify each step but it will be so hard because there will be lots of moves so it will not be possible to check all the move. So Tower of Hanoi is NP Hard problem. Here it is easy to verify the moves but it is hard to make a polynomial algorithm for this problem. [6]
Example 2.
Travelling Salesman Problem [7]
In this problem, if we break the solution into smaller one it will becomes as hard as it was so it will not be easy to solve such type of problem in polynomial time. It also falls under NP Hard problem class. If P becomes equals to NP then it will be easy to travel quicker and cheaper.
Millennium Problem:
Is P=NP? If yes then every problem that can be verify quickly that can be solved quickly too. In Turing Machine, Non deterministic Turing machine and Deterministic Turing machine are equivalent so any problem solvable by deterministic Turing machine in polynomial time is also solvable by non-deterministic Turing machine so we can say
P is subset of NP
But it is hard to make a deterministic Turing Machine for non-deterministic Turing machine. This requires modifications in non-deterministic Turing machine algorithm to get equivalent machine and it also increase the complexity from polynomial to higher.
So P is subset of NP, it has not been proved but by the help of Turing machine concept we can say this only.
But it is not easy to prove because sometime non-deterministic Turing machine is more powerful than deterministic Turing machine.
In Order to solve such Millennium problem, there must exist some problems like
“A problem Z must falls in NP complexity class problem if there exist an algorithm which can solve problem in polynomial amount of time using non-deterministic Turing machine and
Also problem Z must not falls in P complexity class that there should not be any algorithm which can solve such problem Z in polynomial time using deterministic machine.”
But such type of problem does not exists and everybody expects that P complexity class is not equal to NP complexity class.
We saw the example of hotel where verification of problem was easy but solution was very tough. There are several examples which will illustrate how they differs from each other.
Importance of Millennium Problem in Computer Science:
For understanding the importance of this problem.
Let us take an example say Z is the easiest problem from P complexity class, Is Z the correct decryption key for this encrypted file? So it is very easy to check whether it is correct decryption key or not and it is a straight process to check.
When Z is the problem from NP complexity class, which one is correct decryption key from all of these possible keys to this encrypted file?
So problem comes, when the same amount of time is taken by both deterministic machine and non-deterministic?
That is the key in case of P class, deterministic machine will check to decrypt file and tell us whether it is correct or not. And In the same amount of time using same algorithm the non-deterministic machine will try to check each key to decrypt the file.
But it is not true as we know non-deterministic Turing machine are not real and we can make our deterministic machine to work like non-deterministic machine by changing in some of our algorithm but it will not be easy to make changes in algorithm. So breaking an encrypted file is extremely difficult.
If P=NP then for every NP problem there must exist a deterministic machine to calculate the solution in polynomial amount of time. It will be very easy to break the encrypted file in polynomial amount of time.
Advantages:
You must be thinking that how it will help us in computer science when P=NP. It will help us a lot and it will give a new direction to computer science also like all the hard problems which have not been solved yet due to their complexity, can be easily solved in finite amount of time or polynomial amount of time.
For every NP class of problems there must be some algorithm to solve them in polynomial amount of time. It will help while solving Tower of Hanoi problem, travelling salesman problem in polynomial amount of time. The encrypted files can be easily decrypted in finite amount of time as deterministic machines do.
Disadvantages:
If someone proves P=NP then it will have a great effect on internet.it will affect cryptography and other security branches. It will make hacking of anything easy. And there will not be anything like tough code or hard problem in computer science.
Conclusion:
It is an open question since 1971s and still mathematician and computer scientist are trying to give proof that P is not equal to NP class. We have seen so many examples and explanation regarding to prove that P and NP cannot be equal but as technology is developing so fast, it seems that the problem which are taking long time to solve can be solved in finite amount of time by developing fastest processor in future.
