6 ms·
P vs NP: The most important unsolved problem in computer science
- cratermoon 3y agoThis article has the best lay-friendly explanation of what P vs NP means that I've seen.
- EA 3y agoAnd yet it never uses the word "polynomial".
- svat 3y agoIt uses "efficient" everywhere, only alluding to polynomial-time here: > Theoretical computer scientists use a technical definition for “efficient” that can be debated, but it serves as a useful proxy for the colloquial concept. The idea that “polynomial-time” and “efficient” are reasonable proxies for each other is the Cobham–Edmonds thesis: https://en.wikipedia.org/wiki/Cobham%27s_thesis https://en.wikipedia.org/wiki/Cobham%27s_thesis
- krackers 3y agoI don't see how this statement is useful, because if an alg is "tractable" iff it is poly-time then n^10 algorithms would be considered "tractable". I think the real reason we care about P in a CS-theoretic sense is because it's a closed group under various operations, which allows us to talk about things in an implementation-oblivious fashion. In practice in the real world we care only about low-degree P though (usually n < 3 at most), are really interested in linear & nlogn, and care about constant factors. There's also Quasi-Polynomial time algorithms which are interesting because they straddle the line between P and EXPTIME.
- chippiewill 3y agoIt's good purely from being lay-friendly, but I really wish they didn't labour their specific description so much because while it's an intuitive explanation it's also still actually wrong. Also if you're going to write an article that long about P and NP then as the other commenter mentioned, it would be nice to mention the words polynomial and non-deterministic.
- cratermoon 3y ago> still actually wrong Can you be specific about where it's wrong? For the layperson?
- kzrdude 3y agoNon-deterministic should be explained more often because it's meaning in computer science is nonintuitive.
- FranklinMaillot 3y agoI think this video does a much better job. It places the problem in the historical context of computer science and explains why it's an important question. It's also more in depth while still being very short and approachable. I highly recommend the channel if you're interested in information theory. It's just starting to publish new videos after a very long hiatus. https://youtu.be/rK3xcRYLWeg https://youtu.be/rK3xcRYLWeg
- bionhoward 3y agoSpeaking of which, anybody have advice on how to simplify section 2 of this paper and can you please tell me how I’m fooling myself? https://drive.google.com/file/d/1ugJ9czd4EPUPlQO2uGQgsfc6EHWQGFP5/view?usp=drivesdk https://drive.google.com/file/d/1ugJ9czd4EPUPlQO2uGQgsfc6EHW...
- qsort 3y agoWith all the due respect: go study. P, NP, 3-SAT and all the other terms you are using have formal mathematical definitions -- you can't just make stuff up. It's complete nonsense.
- bawolff 3y agoWow, the definitions dont just have the wrong formal definitions, but like the wrong intuitive/informal definitions
- bionhoward 3y agoWhich ones?
- bawolff 3y agoThe definitions of P, NP and polynomial time seem to be wrong.
- bawolff 3y agoIts too incoherent to really understand, but as far as i can tell, i think its a long winded way to beg the question.
- bionhoward 3y agoCan you be more specific? Sorry, I don’t understand how I failed to make an argument, and I certainly didn’t mean for this to be incoherent!
- snek_case 3y agoIs it possible that there's something about the nature of computation that makes it so that P = NP / P != NP is simply unprovable/unknowable?
- bawolff 3y agoYes its possible p vs np is actually undecidable
- sterlind 3y agoif P=NP, could the question still be undecidable? as in, could there be an algorithm for 3SAT that, in practice, happens to be polynomial-time and correct, but there's no way to prove the algorithm's correctness and/or time complexity under any system of formal logic?
- dmurray 3y agoYes, it seems that the state of the art admits this as a possibility (though it seems surprising, and you can make a hand wavy argument dismissing it, as another poster does downthread). Eg this survey by Scott Aaronson: https://www.scottaaronson.com/papers/pnp.pdf#page=26 https://www.scottaaronson.com/papers/pnp.pdf#page=26
- YetAnotherNick 3y agoIt's not impossible to prove P==NP if that is the case as the program is the proof. Also if we assume "if P==NP then there exists program less than a trillion lines" then P!=NP is provable if that is the case.
- joe_the_user 3y agoExhibiting program that terminates in polynomial time for NP problem isn't sufficient to prove P==NP. You also need to actually prove the function terminates in polynomial time. And I could easily imagine that the general problem "does program P(X) terminate in time less than f(X)" is equivalent to the halting problem but in any case it's not at all guaranteed you could create such a proof.
- jostmey 3y agoSounds like a great task for AI to prove as true, false, or unknowable
- wk_end 3y agoAt this juncture there's no reason to think (quite the opposite really) that LLMs are any better at the kind of sophisticated reasoning presumably necessary to prove something like this than human computer scientists are.
- dekhn 3y agoWould answering this question have a real impact on daily life?
- wk_end 3y agoDepends on the answer.
- robot_no_421 3y agoYes, in the sense that if P = NP, it would conceptually be a lot easier in theory to break a lot of public key encryption, which are NP hard problems.
- lesam 3y agoIf P!=NP, probably nothing changes. If P=NP, a very large class of optimization problems probably become practical to solve, which would be a big win for science and technology generally, to the extent that I think it would be felt in daily life. Edit to add: and also as another commenter mentioned, most existing encryption would likely be much easier to break, which would also be felt.
- Almondsetat 3y agoYes, if a polynomial algorithm is found for a single NP-complete problem then any other NP problem can be converted and solved polynomially
- travisjungroth 3y agoI think this is what’s often missing when this topic is quickly presented. And, it makes the whole thing so much easier to understand. If someone were to prove P = NP by showing how to do it efficiently, that would make many computer problems easier to solve. Even problems like “guessing a password”, and that has obvious implications. If we just knew P = NP because a trusted oracle said so, or someone proved it without showing how to do the conversion, or the conversion was impossibly laborious (a constant 2*100 steps) then that changes much less. If someone proved P ≠ NP that would change the least, since that’s how we operate today. It’s not about getting the answer. It’s about what getting the answer suggests.
- xyzzy4747 3y agoShould say the most unimportant. Is there anything practical to gain by solving it?
- jfengel 3y agoProving the equality would be huge. But nobody seriously believes that to be the case. There are no practical consequences of providing something generally assumed to be true. Possibly the proof itself would be enlightening, but without seeing it we cannot guess how. Providing the inequality would reduce the time we spend dealing with cranks, but that's about it.
- markusde 3y agoI disagree that this is an important problem. Even in the unlikely case that some NP-hard algorithm is P, it may be completely infeasible to compute on modern hardware. I'd wager that to certainty be the case if any solution exists at all. I am not aware of any practical use of P=NP outside of pure complexity theory, and the P!=NP case is already ubiquitous assumption anyways. P=NP would be a notable result, but probably not important.
- bawolff 3y agoWhen people say the most important problem in a theoretical discipline, usually its not due to practical applications. That said, there is definitely potential practical implications for this. Even if it means we can know np problems do not have efficient solutions - that is something with practical implications.
- markusde 3y agoEven a P=NP result doesn't tell us that NP problems have efficient solutions. That depends entirely on - if the solution is constructive, - if the asymptotic solution has good constants (lower bound on input size, highest degree term), and - having no other mitigating factors (requiring absurd amounts of space, for example) The idea that P=efficient is a complete misnomer. For simple algorithms, asymptotic analysis is a fine enough coarse-grained view of program performance. However for extreme cases (like may be the case for P=NP) asymptotic analysis tells you almost nothing at all.
- johnday 3y ago> Even a P=NP result doesn't tell us that NP problems have efficient solutions. Yes it does. That is literally exactly what it means. The class P is the class of problems which are considered theoretically "tractable"/"efficiently solvable"/"feasibly solvable" (Cobham-Edmonds thesis). Hence, if NP=P, then that same definition extends to all problems in NP.
- tsimionescu 3y ago
- 0x1ceb00da 3y agoIsn't the answer obvious because of entropy. It's easier to create disorder but much more difficult to create order.
- Tuna-Fish 3y agoNo. This is entirely irrelevant to the problem of P vs NP.