Read on Twitter
Today is #TheoryThursday 
https://abs.twimg.com/emoji/v2/... draggable="false" alt="🧐" title="Gesicht mit Monokel" aria-label="Emoji: Gesicht mit Monokel">!
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...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">
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 hardhttps://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
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.
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 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& #39;s what computers are for!
This is the kind of problem we expect computers to solve easily, right? That& #39;s what computers are for!
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.
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?
But this is a meta-question:
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.
Suppose we have a question of the form:
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.
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.
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.
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.
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?
Now, the P vs NP question, formally, is this:
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.
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 aroundhttps://abs.twimg.com/emoji/v2/... draggable="false" alt="👋" title="Waving hand" aria-label="Emoji: Waving hand">...
We& #39;ll end here for now, but there is so much left to talk about (like NP-completeness).
So stick around
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... class="Emoji" style="height:16px;" src=" 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... class="Emoji" style="height:16px;" src=" 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... class="Emoji" style="height:16px;" src=" https://abs.twimg.com/emoji/v2/... draggable="false" alt="🎥" title="Filmkamera" aria-label="Emoji: Filmkamera"> https://youtu.be/dJUEkjxylBw ">https://youtu.be/dJUEkjxyl...
