Today is #TheoryThursday https://abs.twimg.com/emoji/v2/... draggable="false" alt="🧐" title="Gesicht mit Monokel" aria-label="Emoji: Gesicht mit Monokel">!

Allow me to share with you a previous thread about a fundamental question in Computer Science:

https://abs.twimg.com/emoji/v2/... draggable="false" alt="❓" title="Rotes Fragezeichen-Symbol" aria-label="Emoji: Rotes Fragezeichen-Symbol"> Does P equal NP?

If you have heard of this and want to learn a bit more, read on... https://abs.twimg.com/emoji/v2/... draggable="false" alt="🧵" title="Thread" aria-label="Emoji: Thread">https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
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 https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
One example is the Travelling Salesman problem.

https://abs.twimg.com/emoji/v2/... draggable="false" alt="❓" title="Rotes Fragezeichen-Symbol" aria-label="Emoji: Rotes Fragezeichen-Symbol"> Find a cycle starting in your 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& #39;s what computers are for!
https://abs.twimg.com/emoji/v2/... draggable="false" alt="🙈" title="Nichts sehen-Affe" aria-label="Emoji: Nichts sehen-Affe"> 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& #39;s make it even easier, what about if I simply ask:

https://abs.twimg.com/emoji/v2/... draggable="false" alt="❓" title="Rotes Fragezeichen-Symbol" aria-label="Emoji: Rotes Fragezeichen-Symbol"> Is it possible to visit all cities spending less than X dollars in fuel?

https://abs.twimg.com/emoji/v2/... draggable="false" alt="🙈" title="Nichts sehen-Affe" aria-label="Emoji: Nichts sehen-Affe"> No one still knows an algorithm to answer that question *precisely* for any value of X without trying all cycles, which again is exponential.
https://abs.twimg.com/emoji/v2/... draggable="false" alt="😬" title="Grimasse schneidendes Gesicht" aria-label="Emoji: Grimasse schneidendes Gesicht"> 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:

https://abs.twimg.com/emoji/v2/... draggable="false" alt="❓" title="Rotes Fragezeichen-Symbol" aria-label="Emoji: Rotes Fragezeichen-Symbol"> 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:

https://abs.twimg.com/emoji/v2/... draggable="false" alt="❓" title="Rotes Fragezeichen-Symbol" aria-label="Emoji: Rotes Fragezeichen-Symbol"> Is there an object X with a given property Q?

https://abs.twimg.com/emoji/v2/... draggable="false" alt="👉" title="Rückhand Zeigefinger nach rechts" aria-label="Emoji: Rückhand Zeigefinger nach rechts"> We want to define how hard is this question to answer.
An example of an easy question of this type is the following:

https://abs.twimg.com/emoji/v2/... draggable="false" alt="❓" title="Rotes Fragezeichen-Symbol" aria-label="Emoji: Rotes Fragezeichen-Symbol"> 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.

https://abs.twimg.com/emoji/v2/... draggable="false" alt="🔑" title="Schlüssel" aria-label="Emoji: Schlüssel"> 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:

https://abs.twimg.com/emoji/v2/... draggable="false" alt="👉" title="Rückhand Zeigefinger nach rechts" aria-label="Emoji: Rückhand Zeigefinger nach rechts"> 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.

https://abs.twimg.com/emoji/v2/... draggable="false" alt="🔑" title="Schlüssel" aria-label="Emoji: Schlüssel"> 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& #39;t know yet, but at least they are easy to verify. That& #39;s the key idea.

https://abs.twimg.com/emoji/v2/... draggable="false" alt="⚠️" title="Warnsignal" aria-label="Emoji: Warnsignal"> Note that P problems are also NP.

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

https://abs.twimg.com/emoji/v2/... draggable="false" alt="❓" title="Rotes Fragezeichen-Symbol" aria-label="Emoji: Rotes Fragezeichen-Symbol"> 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.

https://abs.twimg.com/emoji/v2/... draggable="false" alt="🤔" title="Denkendes Gesicht" aria-label="Emoji: Denkendes Gesicht"> Think about what this means for a second, and ask yourself what& #39;s your intuition about it.
What& #39;s the right answer? We still don& #39;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& #39;ll end here for now, but there is so much left to talk about (like NP-completeness). So stick around https://abs.twimg.com/emoji/v2/... draggable="false" alt="👋" title="Winkende Hand" aria-label="Emoji: Winkende Hand">...
As usual, if you like this topic, reply in this thread or @ me at any time. Feel free to https://abs.twimg.com/emoji/v2/... draggable="false" alt="❤️" title="Rotes Herz" aria-label="Emoji: Rotes Herz"> like and https://abs.twimg.com/emoji/v2/... draggable="false" alt="🔁" title="Nach rechts und links zeigende Pfeile in offenem Kreis im Uhrzeigersinn" aria-label="Emoji: Nach rechts und links zeigende Pfeile in offenem Kreis im Uhrzeigersinn"> retweet if you think someone else could benefit from knowing this stuff.

https://abs.twimg.com/emoji/v2/... draggable="false" alt="🧵" title="Thread" aria-label="Emoji: Thread"> Read this thread online at < https://apiad.net/tweetstorms/theorythursday/pnp>">https://apiad.net/tweetstor...
Stay curious https://abs.twimg.com/emoji/v2/... draggable="false" alt="🖖" title="„Live long and prosper!“" aria-label="Emoji: „Live long and prosper!“">:

- https://abs.twimg.com/emoji/v2/... draggable="false" alt="📚" title="Bücher" aria-label="Emoji: Bücher"> < https://dl.acm.org/doi/10.1145/800157.805047>
-">https://dl.acm.org/doi/10.11... https://abs.twimg.com/emoji/v2/... draggable="false" alt="📚" title="Bücher" aria-label="Emoji: Bücher"> < https://dl.acm.org/doi/10.1145/1562164.1562186>
-">https://dl.acm.org/doi/10.11... https://abs.twimg.com/emoji/v2/... draggable="false" alt="📄" title="Seite mit der Schriftseite oben" aria-label="Emoji: Seite mit der Schriftseite oben"> < https://en.wikipedia.org/wiki/P_versus_NP_problem>
-">https://en.wikipedia.org/wiki/P_ve... https://abs.twimg.com/emoji/v2/... draggable="false" alt="🎥" title="Filmkamera" aria-label="Emoji: Filmkamera"> < https://youtu.be/dJUEkjxylBw >">https://youtu.be/dJUEkjxyl...
You can follow @AlejandroPiad.
Tip: mention @twtextapp on a Twitter thread with the keyword “unroll” to get a link to it.

Latest Threads Unrolled:
There are a lot of misconceptions about the Turkish diaspora in Germany. Since i just finished writing an essay about this topic I thought it's time to give other people
Read more
Las mejores calculadoras online en 2020A thread http://totumat.com/2020/11/26/las-mejores-calculadoras-online-en-2020/ Cuando se estudian asignaturas que requieren de cálculos complicados, nada mejor que contar con una buena calculadora.
Read more
Mitigating #ClimateChange is as much about taking up new techs as about leaving others behindMost studies focus on #coal's global downfall but another #energy tech decline is loomingRead my new
Read more