Thread by @AlejandroPiad, Today is #TheoryThursday !I want to talk about what is, possibly, the [...]

Today is #TheoryThursday

!

I want to talk about what is, possibly, the most important question in all of Computer Science: Does P equal NP?

If you have heard of this and want to learn a bit more, read on...

Computer Science is all about finding clever ways to solve difficult problems.

We have found clever algorithms for a bunch of them: sorting stuff, finding shortest paths, solving equations, simulating physics...

But some problems seem to be way too hard

One example is the Travelling Salesman problem.

Find a cycle starting in your home city to visit all major cities in your country and return home with the least fuel cost.

This is the kind of problem we expect computers to solve easily, right? That's what computers are for!

Well, very smart people have tried, and no one has come up with an algorithm that is always better than simply trying all possible cycles.

The problem is that the number of cycles grows exponentially faster than the number of cities!

Let's make it even easier, what about if I simply ask:

Is it possible to visit all cities spending less than X dollars in fuel?

No one still knows an algorithm to answer that question precisely for any value of X without trying all cycles, which again is exponential.

So, are we simply dumb, or is this problem so complex that it is impossible to find a clever algorithm to solve it, in the general case?

This is the root of possibly the most important question in all of Computer Science: P vs NP.

Answering this question is way harder than it seems. You see, most questions in CS are about objects: how to sort, how to compare, how to process...

But this is a meta-question:

Are there questions about objects that are intrinsically very hard to solve?

Stephen Cook tried to answer this question in the early days of Computer Science. He came up with the following definitions:

Suppose we have a question of the form:

Is there an object X with a given property Q?

We want to define how hard is this question to answer.

An example of an easy question of this type is the following:

Given an array of N elements, is there an element smaller than X?

Answering this question is easy. Look at each element, one by one, and compare it with X. It takes at most N steps, for any possible array.

This is an example of a problem in P.

P here means "Polynomial-Time Complexity".

Intuitively, a problem is in P if there is an algorithm to compute a correct answer in polynomial time.

Now back to the Travelling Salesman, suppose I give you an answer:

Yes, here, this is a cycle with cost less than X.

How can you verify that answer is correct? You just add the costs of all edges in the cycle. It takes again N steps.

This is an example of a problem in NP.

NP here means "Non-deterministic Polynomial-Time Complexity".

Intuitively, a problem is in NP if there is an algorithm to verify a correct answer in polynomial time.

P problems are easy to solve. NP problems, we don't know yet, but at least they are easy to verify. That's the key idea.

Note that P problems are also NP.

Now, the P vs NP question, formally, is this:

Are there problems in NP that are not in P?

P vs NP is basically asking if there are problems that are inherently harder to answer than to verify, independently of how smart we become in the future.

Think about what this means for a second, and ask yourself what's your intuition about it.

What's the right answer? We still don't know, but most computer scientists believe that P is not equal to NP.

The reasons are mostly philosophical but there is also evidence that, if P were equal to NP, a lot of weird things would happen.

This question is at the core of Computer Science because it talks about the nature of computation and its inherent limits, regardless of technological improvements.

We'll end here for now, but there is so much left to talk about (like NP-completeness).

So stick around

...