P vs. NP - The Biggest Unsolved Problem in Computer Science by Up and Atom

Video: https://youtu.be/EHp4FPyajKQ?si=4yA88InvCRRUyJ2E

#Math #Discrete_Math #Computer_Science #Algorithms #Complexity_Theory

↩️ Go Back

Table of Contents:

A) Background: The Millennium Prize Problems

The P vs. NP problem has often been called "the biggest unsolved problem in Computer Science"

There is currently a $1 million prize waiting for the person who solves it.

B) But... what is the P vs. NP problem?

The P vs. NP problem can roughly be translated to:
"If a problem is easy to check the solution to, is it also easy to find the solution to?"

This question sounds crazy...

• Why is it even a question in the 1st place?
• What does this have to do with Computer Science?

B.1) Example: Let's play Scrabble! (finding Algorithmic Equivalence)

Let's start by playing a game!

The game is called "Number Scrabble" and it is a 2 player game (1 vs 1).

How to play:

1. We place 9 numbers on the table. (The numbers are in order).

2. Then the 1st player picks a number

3. Then the 2nd player picks a number

4. The aim of the game is to pick 3 numbers that add up to 15. Who ever does this first, WINS!!

5. If all number are picked and no player has exactly 15, the game is a draw.

Now, how would you go about winning this game?

Options:

1. You can try some trial and error. And block the other player from getting to 15.

2. Or, we can "reframe the game"....

Instead of lining up the numbers in a line.

We can arrange them in a square (like a 3x3 matrix) in a VERY specific order...

Now, with the magic square. How would you try to win this game?

Options:

1. we now can try to pick 3 numbers which make a triplet and block the opponent of doing the same.

Now we are playing Tic-Tac-Toe!!!*

When we arrange "Number Scrabble"in a magic square, we see it is really the same game as Tic-Tac-Toe.

A lot of games can be reduced to the exact same game. And a lot of problems in math and computer science can be reduced to the same problem.

But, why is this important?

If 2 problems can be reduced to the same problem, they can be solved by the same strategy.

Any strategy for Tic-Tac-Toe can also solve "Number Scrabble"

B.2) Computational Complexity and Complexity Classes in PSPACE

In Math and Computer Science these "strategies" are called "algorithms". And they are mechanical procedures (like a recipe).

You don't need to think when carrying it out, just follow each step until you've reached the solution.

Note: Depending on the problem, algorithms can be more or less complex

How complicated an algorithm a problem needs to solve is one of the main areas of interest in computer science.

It is so important in fact, that problems are grouped into classed based on how complicated they are.

This area of computer science is called Computationaly Complexity.

And the groups of problems are called Complexity Classes

Each complexity class has its own name. The 2 we are interested in are the:

• Complexity Class P
• Complexity Class NP

"P and NP"are just classes of problems based on how difficult they are to solve.

B.2.1) Complexity Class "P"

Let's see what these classes mean....

P class: It is the class of all problems which have an algorithm that can be computed in "polynomial time". Or in Big O Notation, when the "time complexity" is $O(n^c)$ where $c>1$ and $n$ is the input size.

In other words...
The class P contains all problems a computer can solve in a reasonable amount of time.

Examples:

Keep in mind...

The list of complexity classes is huge!

But we are only discussing these 2 for now...

B.2.2) Complexity Class "NP"

NP class: it is the class of problems that can be verified in "polynomial time" but may take an exponential number of steps to solve. Or in Big O Notation, the "time complexity"is $O(2^n)$ when $n$ is the input size.

Examples:

B.3) What is the important difference between P and NP?

Computers take an extremely long time to solve NP problems...

For example:

If a problem is in the class P and has 100 inputs. And its algorithm is proportional to
$n^3$ (polynomial time).

The algorithm could solve the problem in about 3 hours let's say...

If the problem is in NP class with a completion time proportional to $2^n$ (exporential time).

The algorithm will take roughly 300 quintillion years to solve. That is longer than the age of the universe.

Although NP problems take a very long time to calculate, they also take a relatively short time to verify.

Consider Sudoku!

Sudoku is an NP problem, it takes some effort and time to solve. But once is solved, it is pretty quick to check that it is correct.

C) Let's recap: Does P = NP?

Let's go back to our original question!

We said previously that the P vs. NP problem can roughly be translated to:
"If a problem is easy to check the solution to, is it also easy to find the solution to?"

In other words...
Does P = NP?

What are we really asking here?
We are asking whether complexity classes, P and NP are in fact the same class.

That is, can we perhaps solve these exponential problems in polynomial time?

Why is this even a question?
P and NP seem to be very different things, why would anyone think they are the same?

One reason could because: "since $P\ne NP$ has not been proven, there is still a possibility that $P=NP$, and that is what we want to prove.

Is $P=NP$ ?"
Note: most computer science researchers don't think $P=NP$.

C.1) What would happen if P = NP?

To understand why this is even a question, we should consider what would happen if $P=NP$ ?

Optimization problems like:

1. Transport rooting
   

2. Production of goods
   

3. Job scheduling
   

4. Circuit and database design
   

They are all NP problems, everything would be more efficient if we could find the most optimal solutions to all these problems. Anything that is feasible to check would become feasible to solve.

Other NP problems like "protein folding", would have "polynomial time" solutions and we could cure cancer.

As MIT complexity researcher Scott Aaronson said:

But we would also have some bad news....

Encryption (for banks) and privacy safe all rely on $P\ne NP$.

If $P=NP$ all our passwords and our information would be feasible to get by anyone.

C.2) Has a NP problem ever been solved in Polynomial Time?

Before we continue asking if $P=NP$ ,

Has a NP problem ever been solved in polynomial time?

Let's consider the following problem:
We are given the task to write an algorithm that can "sort" a list of numbers

C2.1) Testing the "Bubble Sort Algorithm"

1st Attempt - A simple algorithm (Bubble sort algorithm).

This algorithm goes through an entire array and compares each neighboring number.

It puts the larger value on the right and the smaller value on the left.

The runtime of this algorithm is of the order of $n^2$.
So, if $n=100$ numbers to be sorted, it will take a maximum of about 10,000 steps to sort the away. But can we do better?

C2.2) Testing the "Merge Sort Algorithm"

2nd Attempt - Divide-and-conquer (Merge Sort algorithm)

This new (recursive) program takes an away, splits it in 2 down the middle, and keeps doing so until there are only squares of 1 left.

Then it takes 2 neighboring squares and sorts them with the lower number on the left and the higher number on the right.

It then looks at the neighboring pairs and compares the lower numbers with each other and sorts them.

Then compares the higher numbers and sorts theme

It does this with all pairs...

And then merges the squares into its previous sub arrays.

And then we repeat the process, we sort and merge until we have a complete array sorted.

Think of it as if the 2 arrays were "competing" to see who has the smaller value, the one who wins gives its number to the bigger sub array.

This new algorithm has a runtime of the order of $nlog(n)$, which mean if there are 100 inputs it'll take around $100log(100)$ = 200 steps to finish.

The Bubble sort algorithm required 10,000 steps and now we can do it with only 200.

This is a massive improvement!

C2.3) Conclusion: From NP realm to the P realm

So... what is the point of this example?
The point is that sometimes you can improve an algorithm so that it solves a problem faster.

The problem didn't change (we are still sorting numbers), but by being clever we found a faster way to do it.

The same happens in the case of SOME NP problems.

It was deemed that they couldn't be solved in polynomial time, but then some clever person came along with an amazing algorithm and managed to transport the problem from the NP realm to the P realm.

Wait...
So if it was shown that SOME NP problems were in fact equal to P, doesn't that prove that $P=NP$?

Ans: No, we need to consider NP Complete Problems (the hardest problems in NP).

C.3) Complexity Classes and NP Complete Problems

Let's review complexity classes:

NP problems can all be solved in exponential time or less.

Some NP problems (those in the P class) can be solved in polynomial time of less.
Therefore, the class P is contained within the class NP.

Some NP problems have been shown to be in the class P,

However, the hardest problems in NP (the NP complete problems), have never been shown to be in the class P.

C.3.1) So, P = NP (complete) is still unsolved...

So the question of whether $P=NP$ still isn't solved, because "NP" actually refers to NP complete problems,

If just one of the NP complete problems was shown to be in the class P, that would mean that all of the NP complete problems would be in the class of P (just like solving "number scrable" also solves Tic-TAC -Toe).

And if some NP problems have been shown to be in class P, it is not to crazy to think that maybe just one NP complete problem might be in the class of P.

Maybe someday someone will come up with an amazing algorithm that can show one NP complete problem being reduced to a P problem.

This would show that all NP problems could be reduced to P problems and that would change the world...

↩️ Go Back

Z) 🗃️ Glossary