# Can you solve the most difficult Computer Science problem?

Category : TECH Author : Gaurav Agarwal Date : Sun Jul 15 2018 Views : 726

# P=NP?

# What is it all about?

The P versus NP problem is a major unsolved problem in computer science. In fact, it is one of the seven “Millennium Prize Problems” selected by the Clay Mathematics Institute to carry a 1,000,000USD prize for the first correct solution. And before we go any further, I must stop you for the love of Alan Turing from putting the value of N as 1 and demanding a million dollars for it and proceed to escort you to the IT department where you belong.

So clearly P and NP are not variables. They are naming conventions to classify problems in computer science based on their difficulty measured in terms of time (number of steps) and space (amount of memory) required to solve the problem.

- P- Polynomial time solving . Problems which can be solved in polynomial time, which take time like O(n), O(n
^{2}) and O(n^{3}). So technically these problems require a lesser amount of resources of a computer due to their low complexity. For example: finding maximum element in an array, checking whether a string is palindrome or not, sorting a given list of numbers, getting a backlog in engineering and many more. You know, the easy stuff.

- NP- Non deterministic Polynomial time solving. Problem which can't be solved in polynomial time. These usually have exponential or other non polynomial complexities like O(2
^{n}) and O(n!). These become particularly more difficult to solve due to higher amount of resources needed to solve them. For example: Solving the Travelling Salesman Problem (you need to try almost all possible paths to find the shortest one) or solving the subset sum problem (you need to try all possible subsets within a given set of integers to find the one whose sum is zero) or finding a girlfriend as a CS major (you most likely won’t find a solution). The difficult stuff.

However, NP problems are checkable in polynomial time which means that given a proposed solution of a problem, we can check that whether the solution is correct or not in polynomial time.

- NP - Hard are a special category of NP problems which may not have solutions verifiable in polynomial time.They may not even be decidable i.e. they might not even have a solution. For example the subset sum problem as explained above - there may not be any subset which adds to zero.

# How do you solve it then?

To attack the P = NP question, the concept of NP-completeness is very useful. If a known NP-complete problem X can be reduced to problem Y in polynomial time and whose solution can still be verified in polynomial time, then Y is also said to be a NP-complete problem.

For example:

we can reduce the Boolean SAT Problem (first NP-complete problem) to the Clique problem and prove the latter to be NP-complete as well.

The SAT problem: “Given a boolean expression, is it satisfiable?” which basically means to find a set of values that cause a given boolean expression to become true.

For example: If the given expression 'x’ is *“a&&(!b)”*, then x is satisfiable (true) when a is true and b is false.

The figure 1 illustrates how the Clique problem (to find a subsets of vertices, all adjacent to each other, also called complete subgraphs) can be reduced from the SAT problem:

Figure 1. The SAT instance (x&&x&&y)||(!x&&!y&&!y)||(~x&&y&&y) reduced to Clique.

Similarly bigger problems like the Travelling Salesman Problem can be proved as NP-complete as shown in figure 2:

Figure 2.

# All you have to do now is:

If any NP-complete problem is in P, then it would follow that P = NP. Thus, if you solve any NP-complete problem in polynomial time, then you solve all other problems reducible to it in polynomial time (P=NP). Conversely, if you prove that there is no possible polynomial time solution to any of the NP-Complete problems, you prove that no polynomial solution exists for any of the NP-complete problems (P ≠ NP).

In either case you solve the great mystery of “P=NP?” and make yourself a million dollars richer and get crowned as the greatest computer scientist in all eternity.

Figure 3.

Euler diagram for P, NP, NP-complete, and NP-hard set of problems.

# So what happens if P=NP?

So, what happens when someone proves P ≠ NP? Well nothing much. People will probably just stop finding polynomial time solutions to all the NP-complete problems and go back to their sad lives.

However, if you prove P=NP, exciting things can happen. All the above mentioned problems could get solved in polynomial time meaning all known computer science problems could be solved immensely faster than ever before, public key cryptography would fail globally as there would be algorithms to get the keys in polynomial time and everything that depends on it would fail (including HTTPS and e-commerce infrastructure), Artificial intelligence would surpass human intelligence, the human genome could be decoded and we could eradicate all diseases known to humanity and make humans immune to any possible spring out in the future. The possibilities would be endless. Heck, even a CS major could finally find a girlfriend (Oh wait. That’s still not happening. Refer NP-hard problems).

According to polls, most computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems.

**However, no one has been able to give a valid proof for P ≠ NP either leaving scope for a proof for P=NP**

# P=NP?

# What is it all about?

The P versus NP problem is a major unsolved problem in computer science. In fact, it is one of the seven “Millennium Prize Problems” selected by the Clay Mathematics Institute to carry a 1,000,000USD prize for the first correct solution. And before we go any further, I must stop you for the love of Alan Turing from putting the value of N as 1 and demanding a million dollars for it and proceed to escort you to the IT department where you belong.

So clearly P and NP are not variables. They are naming conventions to classify problems in computer science based on their difficulty measured in terms of time (number of steps) and space (amount of memory) required to solve the problem.

- P- Polynomial time solving . Problems which can be solved in polynomial time, which take time like O(n), O(n
^{2}) and O(n^{3}). So technically these problems require a lesser amount of resources of a computer due to their low complexity. For example: finding maximum element in an array, checking whether a string is palindrome or not, sorting a given list of numbers, getting a backlog in engineering and many more. You know, the easy stuff.

- NP- Non deterministic Polynomial time solving. Problem which can't be solved in polynomial time. These usually have exponential or other non polynomial complexities like O(2
^{n}) and O(n!). These become particularly more difficult to solve due to higher amount of resources needed to solve them. For example: Solving the Travelling Salesman Problem (you need to try almost all possible paths to find the shortest one) or solving the subset sum problem (you need to try all possible subsets within a given set of integers to find the one whose sum is zero) or finding a girlfriend as a CS major (you most likely won’t find a solution). The difficult stuff.

However, NP problems are checkable in polynomial time which means that given a proposed solution of a problem, we can check that whether the solution is correct or not in polynomial time.

- NP - Hard are a special category of NP problems which may not have solutions verifiable in polynomial time.They may not even be decidable i.e. they might not even have a solution. For example the subset sum problem as explained above - there may not be any subset which adds to zero.

# How do you solve it then?

To attack the P = NP question, the concept of NP-completeness is very useful. If a known NP-complete problem X can be reduced to problem Y in polynomial time and whose solution can still be verified in polynomial time, then Y is also said to be a NP-complete problem.

For example:

we can reduce the Boolean SAT Problem (first NP-complete problem) to the Clique problem and prove the latter to be NP-complete as well.

The SAT problem: “Given a boolean expression, is it satisfiable?” which basically means to find a set of values that cause a given boolean expression to become true.

For example: If the given expression 'x’ is *“a&&(!b)”*, then x is satisfiable (true) when a is true and b is false.

The figure 1 illustrates how the Clique problem (to find a subsets of vertices, all adjacent to each other, also called complete subgraphs) can be reduced from the SAT problem:

Figure 1. The SAT instance (x&&x&&y)||(!x&&!y&&!y)||(~x&&y&&y) reduced to Clique.

Similarly bigger problems like the Travelling Salesman Problem can be proved as NP-complete as shown in figure 2:

Figure 2.

# All you have to do now is:

If any NP-complete problem is in P, then it would follow that P = NP. Thus, if you solve any NP-complete problem in polynomial time, then you solve all other problems reducible to it in polynomial time (P=NP). Conversely, if you prove that there is no possible polynomial time solution to any of the NP-Complete problems, you prove that no polynomial solution exists for any of the NP-complete problems (P ≠ NP).

In either case you solve the great mystery of “P=NP?” and make yourself a million dollars richer and get crowned as the greatest computer scientist in all eternity.

Figure 3.

Euler diagram for P, NP, NP-complete, and NP-hard set of problems.

# So what happens if P=NP?

So, what happens when someone proves P ≠ NP? Well nothing much. People will probably just stop finding polynomial time solutions to all the NP-complete problems and go back to their sad lives.

However, if you prove P=NP, exciting things can happen. All the above mentioned problems could get solved in polynomial time meaning all known computer science problems could be solved immensely faster than ever before, public key cryptography would fail globally as there would be algorithms to get the keys in polynomial time and everything that depends on it would fail (including HTTPS and e-commerce infrastructure), Artificial intelligence would surpass human intelligence, the human genome could be decoded and we could eradicate all diseases known to humanity and make humans immune to any possible spring out in the future. The possibilities would be endless. Heck, even a CS major could finally find a girlfriend (Oh wait. That’s still not happening. Refer NP-hard problems).

According to polls, most computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems.

**However, no one has been able to give a valid proof for P ≠ NP either leaving scope for a proof for P=NP**

**Disclaimer:** The above content reflect author’s personal views and do not reflect the views of OYEWIKI. Neither OYEWIKI nor any person/organization acting on its behalf is liable to accept any legal liability/responsibility for any error/mislead in this information or any information available on the website. This website in no way accepts the responsibility for any loss, injury, damage, discomfort or inconvenience caused as a result of reliance on any information provided on this website.

If you want to add more comments to the article or you see any thing incorrect please write a comment below and we will surely get back to you.