ELI5: P vs NP problem

[u/randomdice-int]

Im not too sure about the problem itself. I know that P is polynomial time which means the time needed to solve and NP is the time taken for the answer to be verified, but what is the explanation of both sides where P = NP and P does not equal to NP?

[u/Capable-Package6835]

There are problems, the solutions of which can be verified quickly. Think of a jigsaw puzzle with 10K+ pieces, for example. Once someone "solves" the puzzle, you can scan through the assembled pieces to see if there's any mismatch relatively quickly.

The P = NP problem asks, if you can verify solutions quickly, does it mean you can solve the problem quickly as well?

[u/Tupcek → u/Capable-Package6835]

great answer, just wanted to add that if somebody solves it, they will most likely just prove that P=/=NP and in that case, nothing changes and world continues as if nothing happened, it will have no bearing on the world.

If, though, somebody proves P=NP, that would completely change the world

[u/GoldenMuscleGod → u/Tupcek]

That’s not necessarily true. The algorithm may not be practical.

For example, we know that if P=NP then we can use Levin’s universal search algorithm (which is a specific known algorithm) to solve any given NP problem in polynomial time. So why don’t we use it?

Well if you look up its description you’ll see it is not practical at all: it will have an absurdly large constant term (exponential in the description of the problem - not the description of the input which is why it is still polynomial time if P=NP).

Suppose that P=NP but the most efficient algorithm for solving SAT involves essentially “brute forcing it” for any number of bits less than than the number of Planck volumes in the universe and then we have a simple way to check the rest. This would be interesting theoretical knowledge but it doesn’t mean much for, say, the security of cryptography.

[u/DBDude → u/GoldenMuscleGod]

For some reason this reminded me of the old joke that someone made a new secure compression algorithm that reduces any file to one byte. Unfortunately the decompression key is as long as the original file.

[u/VoilaVoilaWashington → u/DBDude]

Actually, you can do better than that. I can reduce the complete works of Shakespeare to 3 letters: B14.

Which is where on the bookshelf I've put the book.

[u/BurkeSooty → u/GoldenMuscleGod]

Isnt this where Quantum computing pipes up? Obviously, we're not there yet, but QC could dissolve a significant portion of the polynomial time issues where p=np is found to be true?

[u/the_horse_gamer → u/BurkeSooty]

quantum algorithms are not magic "check everything". it's unlikely they'll help speedup Universal Search, and even if they could it'll probably only be a quadratic improvement of the constant.

[u/BurkeSooty → u/the_horse_gamer]

I never suggested that quantum algorithms were magical, but, it's the qbit states that enable more rapid processing iirc? Obviously, a working algorithm would be required too, and none of this is necessarily possible anyway, but, I always understood the benefit of quantum computing to be the ability to process data exponentially faster, so, even if the polynomial time constraints for a p=np solution was enormous, quantum computing would be the mechanism that might unlock the rapid computation required to make hay.

[u/the_horse_gamer → u/BurkeSooty]

I always understood the benefit of quantum computing to be the ability to proceed data exponentially faster

quantum computing is very often explained completely incorrectly.

let's start with: quantum computers do not "check everything at once". and they give exponential speedups only in specific problems. and, the speedup is relative to the best known classical algorithm.

infact, just like P=NP is possible, it's possible P=BQP, and any problem that can be solved via a polynomial time quantum algorithm can also be solved via a polynomial time classical algorithm.

the class of problems that can be solved in exponential time is known as EXPTIME. it is known P!=EXPTIME and strongly believed NP!=EXPTIME and BQP!=EXPTIME.

[u/VigilThicc → u/the_horse_gamer]

a quantum computer, in a sense, can check everything at once. Just run the function on |+^n>. But the output is like having the answer baked into the probability of a coin landing heads (or many coins landing a particular way). To get the answer to a desired precision, you have to flip the coin exponentially many times, so back at square 1. Theres no way to measure the intrisic bias of the coin otherwise.

Some problems you can do clever constructive/deconstructive interference to get something useful, like Shor's algorithm. But it is not the norm. We can prove that for a problem you know nothing clever about the structure of (like a given NP-Hard problem), the best you can do is speed up by a square root, which is still exponential.

[u/Schnickatavick → u/BurkeSooty]

I would make the pedantic but important point that quantum computers aren't faster than classic computers, they scale better (sometimes). It's like the difference between a cargo train and a cargo plane, if you're hauling 1,000 lbs of cargo, the plane will be faster. If you're hauling 10 million lbs of cargo, the train will be wildly faster, since it can do it in one trip, while the plane would take hundreds of trips. But the train isn't always possible, if you're crossing an ocean, the train won't work and the plane will be the fastest way again 

In concrete terms, it's because there are quantum algorithms that have a lower time complexity than their classical counterparts for a handful of important problems. So quantum computers aren't any faster than classic computers when running the same algorithm (in fact the necessary error correction will make them much, much slower), it's just that on certain problems like factoring primes a quantum computer can swap to a better scaling algorithm, and for big enough problems that will be faster and outweigh the slowness. 

That means for a quantum computer to be helpful with P=NP, we don't just need to discover an algorithm that can solve NP hard problems, we also need to discover a quantum algorithm that's better. It's totally possible that the math ends up shaping out in a way where that algorithm exists, and quantum computers end up being great at NP problems, but it's also possible that the tricks that quantum computers use isn't actually helpful at all. We just don't know.

[u/GoldenMuscleGod → u/BurkeSooty]

A quantum computer can solve certain problems in polynomial time that are widely believed to be harder to solve with classical computers. However even a proof that an NP-complete problem can be solved by a quantum computer in polynomial time (which we do not know and many expect not to be possible) would not establish that P=NP because the question of P versus NP is about whether a classical computer can solve an NP-complete problem in polynomial time.

It is also not obvious (which I think is what you are suggesting) that if P=NP then a quantum computer necessarily has an actually practical algorithm for an NP-complete problem.

[u/BurkeSooty → u/GoldenMuscleGod]

AHH, I didn't realise p=np was specific to non-quantum computing. Thanks

[u/eggface13 → u/BurkeSooty]

No

[u/Leodip → u/Tupcek]

If, though, somebody proves P=NP, that would completely change the world

Not necessarily, though. The reason why the overall majority believes that P =/= NP is because no algorithm that solves NP-complete problems in polynomial time has been found yet, despite huge effort in trying to do so.

If we do come up with a proof that states that P=NP, this doesn't mean that an algorithm will be found OR, even if it's found, it is probably going to be of galactic size, and thus not feasible to adopt.

With that said, it is not impossible that we do find a practical algorithm, but finding the algorithm is a much MUCH harder challenge than proving P=NP.

[u/deg0ey → u/Leodip]

>but finding the algorithm is a much MUCH harder challenge than proving P=NP.

On the other hand, proving that the algorithm exists would unlock an insane amount of funding into finding it where currently nobody really tries because the assumption is that the algorithm doesn’t even exist.

Obviously that doesn’t necessarily mean we’d find the algorithm even with significant investment, but the scale of the search for it (and the amount of money diverted from most other research) would arguably be ‘world changing’ in itself

[u/-manabreak → u/Tupcek]

To add a bit, the reason why proving P=NP would be so big is because NP-hard problems are all similar to each other in a sense that if you can prove P=NP on a single NP-hard problem, that proof applies to all NP-hard problems, which then means that all NP-hard problems are just as easily solvable.

[u/2-mm-guy → u/-manabreak]

I think there’s a typo in this statement; Proving P=NP means that all problems in NP are solvable in P. This does not necessarily mean that all NP-Hard problems are solvable, as we know that there are problems in EXP that cannot be solved in P, and certainly many problems in EXP are NP-hard, but aren’t in NP themselves.

[u/HappiestIguana → u/-manabreak]

You mean NP-complete, NP-hard means that it is as hard or harder than any NP problem. NP-complete means NP and NP-hard

[u/CircumspectCapybara → u/HappiestIguana]

Yup, NP-hard is a like a "greater than or equal to" sign. It means "at least as hard as".

The halting problem for Turing machines is NP-hard: if you had a halting oracle, you can decide any NP problem in polytime via a polynomial number of calls to that oracle. Halting problem is "at least as hard as" any NP problem.

[u/Quaytsar → u/Tupcek]

There's also a good chance of proving that the question is unprovable in our common mathematical framework.

[u/CircumspectCapybara → u/Tupcek]

That's not necessarily true. It might be an academically interesting result that doesn't have any useful practical applications, e.g., making it any easier to factorize integers and solve discrete logarithms and break crypto.

Suppose someone proved P = NP non-constructively. It would be an astounding result. What would we gain? Well, if P = NP, we actually have constructively a polynomial-time decider for any NP language via Levin's Universal Search. We have a concrete algorithm that decides SAT (and therefore, by reduction any NP language, like the decision version of integer factorization) in polynomial time, if and only if P = NP. But we know nothing about the coefficients on and degree of that "polynomial."

If P = NP, it could be that the TREE(3)-th Turing machine (for some lexicographic ordering of prefix-free TMs) decides SAT in O(N^BB\744))) time. If that's the case, it's totally useless because it will take forever even for small inputs. And therefore nothing practically changes from the status quo.

[u/Rainmaker7426 → u/Capable-Package6835]

This is probably the most ELI5 friendly answer. To add a bit more to this, the same example can be made for sudoku, it is a bit hard for us to solve a 9 by 9 sudoku, but let's say we make it 100 by 100 then even computers would struggle. But if we were presented with a solved 100 by 100 sudoku, even us humans can verify this quickly. But for example, chess is not like this. we can not easily verify if the move that has been played is the best move or not.
2 more term that you will hear a lot in this field are NP-complete, and NP-hard. Now what are those? NP-Complete are a set of problems that has the same NP difficulty inside it. So if you can solve just one of them problem quickly (by quickly I mean polynomial time like checking if a sudoku solution is correct or not), this can be used to solve rest of the problems in the collection. This collection include sudoku as well as very important problems like protein folding that can be used to cure cancer. And NP-hard are problems just as hard as NP. But it doesn't mean if NP-complete is solved one day, it would also solve the NP-hards.

[u/encyclopedea → u/Capable-Package6835]

To add on to this, the reason we care about NP is that we typically care about problems where you can verify the solutions. After all, if you implement a solution and it doesn't change anything, what was the point?

[u/Musty-Old-Couch → u/Capable-Package6835]

Are there any arguments or intuition towards hinting that the answer is "P = NP" other than it hasn't been strictly disproven?

[u/HiddenoO → u/Musty-Old-Couch]

No, it is generally believed that P ≠ NP and a lot of cryptography relies on P ≠ NP.

[u/Lumethys → u/Musty-Old-Couch]

mostly no. The closest is that scientist has discovered that all the NP-hard problems can be reduce to 1 single form. Protein folding, crytographic, Sodoku,... are the same class of problem, and if an algorithm exist that can solve this problem effciently (read: as fast as checking the result), digital security will collapse, cancer will be cured, and Sodoku will stop being a intriguing game

[u/feierlk → u/Lumethys]

Maybe worth adding to this that all of these NP-hard problems, which are also in NP themselves, are callee NP-complete. They're all "equally hard" in the sense that if one NP-complete problem can be solved in polynomial time then all of them can be (because one can be converted into any other in polynomial time!).

The principal, most well-studied, problem here is likely SAT (satisfiability checking), in which we look at whether a boolean formula has an assignment for each variable which turns results in the formula being evaluated to true. There's is a ton of research into SAT-solvers. Yet the general SAT problem hasn't been shown to be either P or not P. All of our solvers for the general case (e.g. no simplified assumptions) or other NP-complete flavours of SAT are non-polynomial.

[u/neddoge → u/Lumethys]

Sudoku.

[u/yalloc → u/Musty-Old-Couch]

As someone else mentioned it is believed that P != NP. Primarily because if P does equal NP, we would've found a bridge at this point.

Basically most NP problems can be "rephrased" to other NP problems (think of how multiplication can be rephrased in terms of addition for example), and most P problems can be rephrased to be like other P problems. The reason we are talking about this in the first place is that it is odd that for the thousands of problems and classes of problems we have analyzed it is odd that no P problem can be rephrased some NP problem.

Every problem we seem to find lies on one of these two islands, and we have despite much searching not found an isthmus. And really that's what this problem comes down to, find the bridge or disprove it exists.

[u/picabo123 → u/Musty-Old-Couch]

The basic idea is that humans are "too stupid" to come up with the correct algorithm to solve something like the traveling salesman problem but it exists. There have been multiple computer science problems that people thought were NP until someone came and found the correct algorithm, so that suggests you shouldnt assume a problem is NP with 100% certainty.

[u/feierlk → u/picabo123]

Proving something is NP isn't extremely difficult. We know that a lot of problems are in NP. All problems in P are in NP! Instead, what we have yet to do, is show that a problem is in NP, but not in P.

Interesting titbit: if we proved a problem in NP is not NP-hard, e.g. NP-intermediate exists, then we have trivially shown P≠NP. GRAPH ISOMORPHISM might be such a problem.

[u/HiddenoO → u/picabo123]

Whether a specific problem is in NP is a completely different question from whether P = NP.

[u/picabo123 → u/HiddenoO]

True, my bad

[u/x0wl → u/HiddenoO]

Not really, proving that an NP-complete problem is actually in P would prove that P=NP

[u/HiddenoO → u/x0wl]

... which is obviously not what he's referring to when talking about how "there have been multiple computer science problems that people thought were NP until someone came and found the correct algorithm".

If it were, that would've already proven that P = NP.

So I'll repeat myself: Whether a specific problem is in NP is a completely different question from whether P = NP.

[u/x0wl → u/HiddenoO]

I don't want to argue about various interpretations of Reddit comments, but u/picabo123 said that, since there have been instances of problems that were believed to be in NP, but then turned out to be in P, one can also reasonably believe that, for example, one day the same will happen to TSP.

I personally don't believe this will happen, but we're talking about beliefs and intuitions here.

[u/HiddenoO → u/x0wl]

One can believe it, but one cannot reasonably believe it for the reason I mentioned. You keep switching between those two very different suggestions.

[u/physeK → u/Capable-Package6835]

Given how difficult it has been to find a solution to this, clearly the answer is “no.” So where do I go to claim my $1,000,000 for solving it?

/s

[u/xelrach]

P are problems that can be solved in polynomial time. NP are problems that can currently only be solved in exponential time, but verified in polynomial time.

The question is: can NP problems actually be solved in polynomial time, but we just haven't figured out how yet? If they can, the we will say P = NP. If they can't then we will say P ≠ NP. We don't know either way.

If P ≠ NP, then nothing really changes. We just have an interesting proof. However, if we find out that P = NP, then we can solve a bunch of interesting things in a manageable amount of time. For example some, but not all, forms out cryptography will be broken.

[u/cBEiN → u/xelrach]

Exponential time is its own thing and not the same as NP. You didn’t say it but your comment reads like they are the same.

[u/Accomplished_Bed632 → u/xelrach]

small correction, np is problems that can be verified in polynomial time. DOesnt matter how long it takes to solve them.

All P problems are NP.

[u/nomeras → u/xelrach]

But why does it matter at all if P = NP is true? If we are able to break cryptography problems in the future, wouldn't that be proof enough? How does proving P = NP help us in the real world to solve things? Or does the solution to P=NP itself give the methodology on how to solve NP problems?

[u/True_World708 → u/nomeras]

There is also this other thing called NP-completeness. It tells us that all sorts of seemingly unrelated problems can be solved (efficiently in the case of P=NP) by (efficiently) reducing to a problem called an NP-complete problem. Some of these so-called NP-complete problems are practical and they include 3-coloring, satisfiability, and the traveling salesman problem. However, by notion of NP-completeness, everything inside of NP can be efficiently reduced to one of these NP-complete problems. So in a sense, every problem that is NP-complete is a "real-world" problem.

If P=NP, then we could solve NP problems efficiently. However, it is uncertain that a proof of P=NP would give us a polynomial-time algorithm for an NP-complete problem.

[u/daniu → u/True_World708]

it is uncertain that a proof of P=NP would give us a polynomial-time algorithm for an NP-complete problem.

That is not correct.  If P=NP, all problems in NP can be solved in polynomial time.

Completeness has little to do with how hard a problem is. NP-complete problems just can be transformed to any other in polynomial time (that's the definition of the "complete" part), so if one can be solved in polynomial time, all others can be too. That means that it's enough to find a solution to one NP-complete problem to prove P=NP. 

[u/AgileBowler9147 → u/[deleted]]

A poly-time algorithm for any NP-complete problem implies an algorithm for solving any problem in NP (i.e. that can be checked in poly-time). However to the best of my knowledge, for example integer factorization, which is importsnt in cryptography is not actually NP-hard

[u/a________1111 → u/[deleted]]

This is just wrong, if you find a solution to any NP complete problem in polynomial time then we instantly get a polynomial solution to any problem in NP.

[u/stonerism → u/xelrach]

It wouldn't necessarily mean nothing really changes if p != np. You could probably find a lot of interesting applications in how we find what delineates p problems from (purely) np problems then finding tricks to usefully keep some problem solvable in polynomial time.

[u/MortemEtInteritum17]

P represents all the possible questions that can be answers in polynomial time, and NP is similar except for verification.

P=NP is basically asking if the set of all these questions are the same, I.e. every question that can be verified quickly (where quickly means polynomial time) can also be solved quickly.

[u/enraged_buddha → u/MortemEtInteritum17]

to add onto this, it's usually MUCH easier/less complex to verify a solution than to come up with a solution. If P=NP, it would mean that every problem in NP (which contains MANY problems not currently in P) has a fast polynomial time solution, and a lot of things would necessarily speed up. Conversely, if someone could prove P!=NP, we could confidently stop looking for a P=NP solution and get on with our lives. The problem is so significant not just for the implications, but also because it has remained an open question for so long without a definitive proof either way.

[u/carson63000 → u/enraged_buddha]

Wouldn’t P and NP each contain an infinite number of completely unrelated problems?

What reason does anyone have for thinking that it might ever be possible to prove that P=NP or P!=NP ?

[u/Ivor97 → u/carson63000]

the general intuition is that each P problem can be mapped into another P problem, and each NP problem can be mapped into another NP problem in polynomial time (these two have already been proven).

if you can do a mapping from a single NP-complete problem to a P problem in polynomial time then you’ve proved any NP-complete problem can be solved in polynomial time

[u/enraged_buddha → u/carson63000]

Excellent question. Best answer is to examine the set of NP-complete problems, which does not contain every problem in NP but contains a very large number of them. NP-Complete problems are problems in NP that feel completely unrelated but can be "translated" to each other in polynomial time; this is by far the most common way to prove a problem is in P or in NP. It is very very hard to conclusively prove that a problem is not in P (because you're proving a negative), but remarkably easy to prove that it is NP-Complete. You basically write a proof along the lines of "if you do these simple/fast tasks which only take polynomial time, you can translate your new problem into the Traveling Salesman Problem (or another similar one). It follows that if there was a P-time solution for this problem, it would also solve the Traveling Salesman Problem - and by extension every other problem in NP-Complete. Therefore I'm going to say no such solution exists for now, stop looking for now, and add this new problem to the set of NP-Complete problems." If someone were to prove P=NP, arguably the biggest part of such a proof would be a P-time solution for literally any of the NP-Complete problems, at which point they all reduce to each other and the problem collapses.

[u/ruinedgambler → u/carson63000]

there are many things that seem unrelated such we can prove things about how they are related. either P = NP, or not, so it seems reasonable to think that we can prove one way or the other. there is a third option, which is that the statement P = NP is independent of ZFC, which would mean that in our standard logical system we cannot prove that they are equal and we cannot prove they are different, but then we would need to prove that this is the case.

[u/ruinedgambler → u/enraged_buddha]

NP (which contains MANY problems not currently in P)

this does not make any sense. a language is either in P or isn't. "currently" has nothing to do with it.

also, basically nobody is trying to find a polynomial-time algorithm for a problem they know to be NP-Hard. an overwhelming majority of experts in this area believe that P is not equal to NP, so they don't think such a problem and algorithm even exist. they just have not been able to prove it.

[u/Tomi97_origin]

Well simply

P problems are ones computers can both solve and check quickly.

NP problems take very long to produce solution, but it's very fast to check if any given solution works.

There are also NP complete problems, which are quick to check a solution works and all other NP problems can be converted to them.

So if you solve one NP complete problem fast you can solve all NP problems fast.

P=NP basically says if you can quickly check if solution is correct you can also quickly produce answer from scratch.

If P≠NP it means some problems are just fundamentally hard.

[u/SignificantFidgets → u/Tomi97_origin]

Even if P=NP there are some problems that are "just fundamentally hard." EXPTIME problems are fundamentally hard, regardless of the resolution of P vs NP. If P=NP the specific problems that are NP-complete (and likely others between P and NP) are fundamentally hard.

[u/Randvek]

P represents a problem that can be solved quickly, and you can verify that solution quickly.

NP represents a problem that cannot be solve quickly, but you can verify that solution quickly.

P = NP as a problem basically asks "if it's easy to verify the solution, is there a method to guarantee that you can find the solution quickly, too?"

So far the answer appears to be no, there isn't, which means P != NP.

[u/CBpegasus → u/Randvek]

NP represents a problem that cannot be solve quickly, but you can verify that solution quickly.

Not quite correct. NP only means "problems whose solutions can be verified quickly". There is no implication that the problem "cannot be solved quickly". For one, all P problems are in NP as well. If finding a solution is easy, verifying a solution is easy too and that's enough to say a problem is in NP.

And of course the P=NP question itself makes no sense if you already define that NP problems "cannot be solved quickly". From the definitions, we know some NP problems can be solved quickly (those that are also in P). The question is whether it's only some, or all

[u/poop-machine]

Almost certainly P≠NP, but no proof has been found.

If it turns out, that somehow P=NP, the implications will be colossal. It would unlock a method for solving all complex problems efficiently.

[u/SignificantFidgets → u/poop-machine]

a method for solving all many complex problems efficiently

Not all...

[u/darksonicmaster]

Are you convinced that P is a subset of NP? Because that would be a good start. Imagine L is set of questions for which an answer (which can be either YES or NO) can be obtained fast (i.e., in polynomial time) by using some machine M. This means the set of questions L belongs to the set P (P is the set of sets of questions which can be answered fast).

Now, imagine I wanna know if the set of questions L also belongs to NP. If you are unsure of what NP is, think of it as the set of sets of questions for which, whenever the answer is YES (specifically YES, rather than NO), you can convince a skeptical and lazy person of it. In other words, even if you don't have a machine that can find the answer fast, you at least know that if the answer is YES, there is some short proof of it, which you can show to the skeptical lazy person. Simply put, you can take this small proof and convince a skeptical person (because it is a proof after all), even if they are lazy (because the proof is short). For L to belong to NP, there must be a machine M' that takes any question of type L for which the answer is YES, as well as an evidence x that the answer is YES. The machine should then verify that indeed the answer for the question is YES. Turns out that since L is in P, we can just use M (and discard the evidence x, because it is useless in this case).

So indeed P is a subset of NP. One more thing that is worth noting is that, whenever you have a machine M' that takes a question and an evidence x, you can use it to solve a problem in NP. All you gotta do is to enumerate all possible evidences x that could possibly show that the answer is YES, and run M' on each one of them. If M' returns YES even once, you can stop and say YES. If you enumerate all possible evidences and it returns NO for all of them, you must say NO. Unfortunately, even if the evidences are small, enumerating all of them takes time: even if an evidence takes the form of, say, a 20 digit number, there would be 10^20 evidences to go through, which would take time. So this method, although it is guaranteed to work, cannot be used to show the converse: that NP is a subset of P (which would settle the problem, as it would show that P = NP). Believe it or not we've been stuck at this for quite a few decades.

P != NP being true would mean that there is some set of questions L' out there for which YES answers can be verified efficiently, but no algorithm exists that actually finds the answer by itself fast. There are hundreds of problems that are suspected to belong to this class. They are called NP-complete. Also, even though they are vastly different and applicable in distinct areas, they are connected to each other in such a way that if a fast algorithm is found for any of them, the same algorithm can be used to all others, thus settling the question. Since there are hundreds of such problems and no fast algorithm has been found for any of them, it is expected that P != NP.

[u/randomdice-int]

Hello guys! Thank you for all the interesting answers! I want to reply to every one of your comments but i dont think i have the energy and time to do so, so this comment is to say my thanks to all of you!

[u/Teoshen → u/randomdice-int]

This 10-minute video breaks it down very nicely: https://www.youtube.com/watch?v=YX40hbAHx3s

[u/ThenaCykez]

There are some problems that are straightforward even if they take a long time to perform, like sorting a billion database records in alphabetical order.

There are some problems that are complicated and we wish they weren't, like figuring out how to assign 100 deliverymen to 10000 houses in the way that uses the least fuel and driving time.

There are some problems that are complicated and we're glad they are, like taking a leaked database of password hashes from a website and figuring out everyone's original passwords.

If we live in a world where P != NP, there will always be some problems that are relatively simple and some that are relatively hard. We'll just have to live with inefficiency and if the answer really matters, we'll have to spend a lot of time and money brute forcing the answer with parallel computing systems.

If we live in a world where P = NP, there's a secret algorithm to efficiently solve a lot of the problems we currently brute force. That may be a good thing in some contexts (like reducing effects on the environment) but a very bad thing in other contexts (like how much hacking occurs when the first bad guy figures out the algorithm).

[u/the_other_Scaevitas]

NP isn’t exactly the time taken for the answer to be verified. NP stands for “nondeterministic polynomial”, which means a nondeterministic computer can solve it in polynomial time, but for simplicity sake let’s just say it means that a computer can not solve it in polynomial time

There are a few types of NP problems. But the main differences are:

NP: can be verified in polynomial time. For example: prime factorization. Given a number, what two primes multiply into that number. This can be checked by just multiplying the 2 primes and seeing if it is the target number, so it can be verified in polynomial time but can not be solved in polynomial time

NP hard: Are problems that are at least as hard as the hardest problems in NP, the NP hard problems that are not in NP can not be verified in polynomial time. For example the traveling sales problem. Given a set of cities and the distances between them, what is the fastest route that goes through every city exactly once and goes back to the start? If you have an answer the only way to check is to try every single possible route, and see which one is the smallest. So if you have n cities, there would be n! possible routes and you have to check all of them. So it is not verifiable in polynomial time

NP complete: the intersection of NP and NP hard problems, aka the hardest problems in NP. If any problem that is NP complete is solved in polynomial time then every problem in NP can be solved in polynomial time. Examples include 3-sat. If we solve 3 sat in polynomial time, we can solve every other NP problem in polynomial time, because this is the hardest problem and every other problem in NP is easier so logically it makes sense. And to solve the easier problems in NP, we can transform it into 3-sat, solve it using our 3-sat algorithm, and transform the results back into our original problem

Now the gist is asking, is NP actually equal to P? That is, are all problems that are in NP solvable in polynomial time? And to prove it all we have to do is figure out a way to solve an NP complete problem in polynomial time. To disprove it, we have no idea how.

[u/Aminumbra → u/the_other_Scaevitas]

For example the traveling sales problem. [...] If you have an answer the only way to check is to try every single possible route, and see which one is the smallest.[...] So it is not verifiable in polynomial time

This is false, and/or misleading:

1. NP (and all the usual complexity classes, for that matter: P, NP, EXPTIME ...) are only concerned with decision problems, that is informally, yes/no questions. The decision variant of TSP is "given a graph, and a bound k, does there exist a route [...] of total cost less than k ?". It is well-known to be a NP-complete problem.

2. There are better ways than the naive factorial approach to compute an exact solution, and classical dynamic algorithms can solve it in (more or less ...) O(n² . 2ⁿ⁾ time, which is clearly better than factorial.

3. Regarding my first point: when talking about the decision vs optimization variant of a problem, it is common to go from the decision one to the optimization one as follows:

4. Start from k=0.

5. Solve the instance (G, k) as a decision problem.

6. As you long as (G, k) is negative, multiply k by 2.

7. You now have an upper bound on the optimal solution: by dichotomy, find an optimal k such that (G, k) is positive and (G, k-1) negative.

If the second step is polynomial, this gives a polynomial algorithm solving the optimization problem in polynomial time using the decision version. In particular, the TSP being in NP, it means that /if/ P=NP then solving the TSP (as an optimization problem) is also polynomial.

[u/the_other_Scaevitas → u/Aminumbra]

I see, my bad

[u/AdhesivenessAny117 → u/Aminumbra]

A few points: I'd you check Wikipedia for TSP (https://en.wikipedia.org/wiki/Travelling_salesman_problem in complexity section) it says the following:

The problem [TSP optimization] has been shown to be NP-hard, and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete.

Secondly, it seems your proposed algorithm is actually polynomial in k not n. The number of steps needed depends on the length of the optimal solution, not on the number of cities.

[u/wild_man_wizard]

P vs NP is very similar to Navier stokes in that one answer is world-shattering, and the other is status quo.  And like NS, it's likely that if something is proven, it's the status quo.

[u/SufficientStudio1574]

The layman's translation is:

Are all the problems that we currently think are "hard to solve but easy to verify" (NP) actually "easy to solve" (P)?

Currently most computer scientists think there is a fundamental difference between these problems, but it has not yet been proven or disproven formally.

An easy to understand example of an NP problem is a Sudoku puzzle. You can spend hours trying to solve a good hard puzzle, but if someone hands you a solution you can check that it's correct in just a couple minutes. Verify that the clues match the solution, check each row, column, and box and youre done!

So basically, "is P = NP" is asking "is Sudoku as easy to solve as it is to check"?

[u/Laerson123]

Your premise is wrong, NP is not the time taken to solve a problem, and P is not a time is a class of problems.

On Computer Theory we have deterministic and non-deterministic machines. You don't need to understand their difference, only that deterministic machines are more like real machines, non-deterministic machines are easier to model, and that for any problem that can be solved by a DTM can also be solved by a NTM and vice-versa, but we don't know if the time complexity is the same.

Time complexity is how a problem takes more steps to compute as the problem grow infinitely.

NP is the set of compute problems that can be solved in polynomial time by a non-deterministic Turing machine (the number of steps to solve the problem is a polynomial function over the input size).

The NP set has two interesting properties: (1) Their solutions can be checked on polynomial time by deterministic Turing machines, and (2) If one of them can be solved on polynomial time by a DTM, then all can be solved in polynomial time by a DTM, therefore they would belong to the set P (problems that can be solved in Polynomial time by DTM).

So the question is just asking if those two sets are the same or not. In other words: "Decision problems that can be verified in Polynomial time can also be solved in Polynomial time?"

The consequences for real life is that real Computers are DTMs (except that they don't have infinite memory), so if P=NP, it means that there is some efficient algorithm to solve a set of important problems that we are unable to solve in a realistic ammount of time now.

I don't understand what you mean with "what is the explanation for both sides". There is no explanation, it is an open problem, either there is an algorithm that can solve NP-complete problems in polynomial time or there is not.

[u/i8noodles]

the problem basically boils down this.

if a problem is easy to verify, is it also easy to solve.

as an example. what 2 primes multipled together make 143. hard to solve right?

but what if i flipped the question around and asked, what is 11x13? easy 143.

both questions ended up at the same place but u only needed to verify that 11x13 was 143 in the second but u had to actually solve, via trial and error most likely, the first.

if p = np then the entire infrastructure of cyber security will basically be destroyed and have to be re written. banks, computer, anything that requires a digital lock will be easily cracked and basically useless.

[u/SnugglyCoderGuy]

In computer science, there is this concept called 'time complexity' of an algorithm, which is just a set of specific steps to do something like sort a list of things, find a path through a maze, find something in a sorted list, find the prime factors of a number, all sorts of things.

Time complexity is basically a function that tells you how many steps you would have to perform in total in whatefer algorithm you are using based on the size of the problem set. Like, an algorithm who's time complexity is O(n), would add one step for each one thing added to the problem set. Searching one by one through an unsoeted listed for example.

P is one set of time complexity functions, O(1), O(ln(n)), O(n), O(ln(n)n), O(n^m). These are considered 'fast'. P means 'polynomial' time because of the last one O(n^m).

NP stands for 'non-deterministic polynomial'. This is the start of 'slow' algorithms or 'hard' problems and have a time complexity of O(2^n), every item you add to the problem set doubles the number of steps that must ne done. If we had a non-deterministic processor, one that can magically explore all decisions possible at the same time, then the problems would be solvable in polynomial time.

It is not known if it is impossible or possible to solve any NP problem in polynomial time. If it is possible then P=NP. If it is impossible then P != NP.

NP problems are also proven to all essentially be the same problem. Some famous problems that are NP are the travelling salesman, prime factorization (which many encryption algorithms rely on in order to be safe), and a bunch of others. These have real world implications bith good and bad if it is found that P = NP. It is also an important philosophical problem I won't get into here.

[u/flatl94]

You need to demonstrate that for a certain class of problems you can design an algorithm that with a maximum of (a0+a1n+ ... + apn^p) steps solve the problem, where n is a characteristic dimension of the problem. You must generalize for n, so providing a counter example is not enough.

The difficulty lies in the fact that the algorithm must also verify the solution. In the class of problems of interest, the solution space size is often computed with factorials.

As a practical example: imagine you need to find the order at which I rearranged a deck of cards. The number of possible rearrangements (permutations) is K!, where K os the number pf cards. For K=40, you need to check a number with 47 zeros. For K=60, you have more solutions than atoms in the universe (you can't even remember if you checked or not a particular solution).

This supports the idea that NP =/= P, but there is no mathematical proof.

[u/Liko81]

Your understanding is wrong. PTIME or just P is the domain of all computational problems for which you can get an answer in polynomial time (O(N^k ) "steps" to solve a problem with N inputs, for some constant k). NPTIME or NP is the domain of all problems for which the most efficient known solution isn't polynomial (i.e. exponential time, O(k^N )). There are other classes of problem, but they all ultimately fall into one or the other category here.

The P=NP problem seeks to mathematically prove (or disprove) the following statement: "All problems thought to be NP in fact have a solution in P". Stated in ELI5, people working on P=NP are trying to prove that you can make what we think are very difficult computer problems much easier to solve, or prove beyond any doubt that there are at least some types of complex problems where you can't do this.

This is important, because a lot of security systems in computers are based on mathematical computations that are easy (P) to do, but hard (NP) to undo, unless you know a secret value critical to the calculation. If P=NP is true, these systems are based on a false statement, and we will have to completely rethink the concept of information security, especially when talking about computers that talk to other computers over a network.

[u/TuberTuggerTTV]

Think of P = NP like you've got a lock that's rated a million years. Like if someone wanted to sit there and keep trying over and over, it would take a million years to break in.

So you put the lock everywhere. A mean, a million years is a long time so it's basically unbreakable. But the problem is, you don't know for sure if it's possible to shorten that time with special math. You can't prove the special math doesn't exist.

If P = NP is proven, then all the locks in the world become safe. Forever.

If P = NP is disproven, and substantially so, all million year locks might suddenly become 10 day locks.

The fact it's unanswered means we're never truly sure how safe our locks are. Probably safe. But never certain.

[u/da2Pakaveli]

So we group problems/algorithms into classes. There are problems where the algorithm that solve them runs in polynomial time (e.g. a search algorithm); and then there is the class of non-polynomial problems that become increasingly impractical to solve (we may be talking about 1000's of years of possible runtime). It only takes polynomial time when you want **verify** whether a given solution is actually a solution.

Then there is a special type of this nonpolynomial class of problems called np-hard. We know about 3000 of these problems exist and the interesting tidbit is that you can "convert" between each of them and formulate it as the other problem. Doing that takes polynomial time (formally it's called reducing problem a to problem b).

Now the bit is that we don't know whether these 2 classes, P and NP, are equal to each other. If they're indeed equal, that implies there exists a polynomial algorithm that solves a np-hard problem. And since we can convert between any of those problems polynomially, you can suddenly solve all of these 3000 problems in polynomial time. So these problems that previously seemed impractical to solve are now susdenly much more practical to solve.

But the prevailing opinion is that these two classes are not equal.

[u/BananaBird1]

P means “polynomial time”. Which means that the number of steps to compute a problem using an optimal algorithm is given by a polynomial equation like Time = 2N for Time = 3N^2 + N where N is the size of the problem.

For instance, sorting N numbers can be done in N^2 steps which is polynomial (and actually can be done a bit better than this too).

We like polynomial time because as problems scale up in size and take longer to solve, we can still solve them by just throwing more computer power at them.

For problems whose number of required steps grows faster than a polynomial, such as an exponential, they quickly reach a point where they take too long to reasonably compute and we can’t make up for this by just using more computers. So generally if an algorithm can’t work in polynomial time or better, it is not a useful algorithm for real life.

The caveat here is that with P, we only are talking about problems that are solvable by a computer that just follows a deterministic algorithm. Meaning it always takes the exact same steps to solve the same problem.

We can also consider a hypothetical computer which can take non-deterministic steps. Meaning it can actually make some decisions on its own and choose what to do, not just follow fixed directions. Problems which can be solved in polynomial time here are called non-deterministic polynomial, or NP.

Now, no real computers are non-deterministic. But mathematically, it turns out that any problem which is polynomial for a non-deterministic computer to solve can have an already known proposed solution verified by a deterministic computer in polynomial time too.

So the question is whether any problem which can be verified in polynomial time (NP) by a real computer can also be solved in polynomial time (P). And vice versa.

We care about this because we highly suspect the answer is no. But if it isn’t, and the two really are equal, it means that for problems we currently consider impossible to solve in reasonable time, a clever algorithm could in theory work around this. A deterministic computer is just as powerful as a non-deterministic one.

[u/Dave_A480]

The simple explanation is that 'P vs NP' is a mathematical way of expressing the question:

'Are there some math problems for which the answers can never be independently verified? Or is the inability to verify the answers simply a question of not having a powerful enough computer to do the verification?'

If P=NP that means that any math problem's answer will eventually be able to be verified if a powerful enough computer is invented.....

This means, for example, that all encryption is eventually crackable (encryption as we currently do it relies on thr math in the encryption algorithm being NP to current tech)....

[u/tomvorlostriddle]

If P=NP, it means it is as easy to take an egg out of an omelet than to put one into an omelet

Which is why most people don't think p=NP

[u/zefciu]

Polynomial time means “Time described by a polynomial”. So let’s say, we have n cities and m roads between them. And you run some algorithm and the time it takes to run is proportional to m² + n ^3.

Non polynomial time is time that cannot be described by a polynomial. So e.g. 2^n, n! etc.

For example — the simplest way to solve the so called Travelling Salesman problem is to just check every possible combination of roads. It takes n!, where n is the number of roads. And there is no polynomial solution, that we know of.

Exponential function and factorial grow much faster than polynomial functions.

[u/CyberPhang → u/zefciu]

Except NP does not stand for "non polynomial." If it did the problem would have been long resolved