11 ms·
Complexity theory’s 50-year journey to the limits of knowledge
- PartiallyTyped 3y agoThis is easily one of the most well written articles published by quanta. Truly a pleasure to read.
- xmonkee 3y agoYeah, a lot of love went into this. Could be made into a book, i would buy.
- guga42k 3y agonitpick: I wonder how TSP became NP complete. It would require to polynomial time algorithm to validate the solution. I doubt such algorithm does exist.
- teraflop 3y agoYes, TSP is in NP. Strictly speaking, the only problems in NP are decision problems, so when we say "TSP is in NP", we're talking about the "decision version of TSP": given a graph G, does there exist a Hamiltonian circuit with total length <= K? And it's straightforward to show that this problem is in NP, because if the answer is "yes", then simply exhibiting such a tour is enough to provide a polynomial-time-verifiable proof of the answer's correctness. (Note that it is not known whether TSP is in co-NP, so it is not known whether one can produce a polynomial-time-verifiable proof of a "no" answer.) But note that if it were to turn out that the decision version of TSP was solvable in polynomial time, then the optimization version would also be in P, because you can just binary-search on all of the possible values of K. This results in at most a polynomial slowdown.
- bumbledraven 3y ago> Suppose that P = NP. To prove it, researchers would need to find a fast algorithm for an NP-complete problem, which might be hiding in some obscure corner of that vast landscape. They wouldn't need to find such an algorithm. They would just need to prove that such an algorithm exists.
- wddkcs 3y agoCan you really separate the two? For something like NP-completeness, I'm having trouble conceptualizing how a proof for existence would not require demonstration.
- fooker 3y agoYes, proofs don't have to be constructive. Consider proofs by contradiction, you could potentially show that if such an algorithm does not exist some important true statement would be rendered false.
- viscountchocula 3y agoSure. There is definitely a googolth digit of pi. Computing what the digit is, however, is not necessary to prove that such a digit exists.
- wddkcs 3y agoMy intuition was that if a proof for P = NP exists, it would be incomparable to the kind of Pi example you provide- Pi is defined as an irrational ratio, so the existence of whether x digit of Pi exists. It would instead be like saying, 'the x digit of P is 7, and here is a proof that is not a straight calculation'. The idea of a proof which can demonstrate knowledge of X digit of Pi, without verification, doesn't click for me.
- raincole 3y agoIt's a quite bad analogy because the googolth digit of pi is completely constructive. (You don't need to calculate it, but it is constructive) P = NP proof could be not constructive.
- archgoon 3y ago[dead]
- paulddraper 3y ago
- PartiallyTyped 3y agoIs there a missed connection between entropy and circuit complexity? It looks like one might be able to draw some parallels between the two. Other thoughts; it's interesting that PvsNP is essentially about the lengths of proofs, and thus it is the task of deciding in poly time whether you can decide all decidable problems whose proofs are polynomial to their encoding.
- Q6T46nT668w6i3m 3y agoThis is addressed, rather extensively, in the article.
- PartiallyTyped 3y agoEntropy or it beying a metaproof?
- PartiallyTyped 3y agobeing*
- tetrazine 3y agoThis is an aside. But I twigged on a caption for one of the figures: “Every computational problem takes longer to solve as its input grows larger, but not all problems grow harder at the same rate.” It’s obvious from CS201 that this phrase is generally true and I have no pedantic objection to its inclusion in the article. However, I’m curious if this is strictly true or if we can find a (nontrivial) counterexample. Are there any algorithms that run faster as input grows? My first intuition is some kind of probabilistic question solved to a given correctness bound. Edit: it is trivial to construct an algorithm with this property. My precise question is whether any meaningful problems have optimal algorithms with this property.
- Q6T46nT668w6i3m 3y agoOf course. The obvious examples are probabilistic, e.g., Monte Carlo methods, as an increase in the problem space decreases the number of samples needed.
- Filligree 3y agoI could imagine some behaviour along those lines in search engines, specifically if you're searching for similar documents. Which none of them seem to — would be useful! Let me know if I'm wrong! — but imagine a search engine that lets you look for documents 'similar to this document here'. Also imagine that's threshold-based; you want equal levels of similarity regardless of the rarity of the input document. In that case, as the size of the corpus grows it should get easier to find ones in the right range of similarity.
- downWidOutaFite 3y agocaches? the more input the fewer cache misses
- mjcohen 3y agoDepends what you mean by larger. The example that occurs to me is the priblem of determining whether or not an integer is prime. This can be done relatively quickly for numbers of the form 2^p-1 where p is prime, but would take much longer for a much smaller prime not of this form.
- canvascritic 3y agoOne thing I've always found fascinating is the relationship between quantum computing and complexity classes. With the promise of quantum computers solving certain problems exponentially faster, it'll be interesting to see how they fit into our established P vs. NP paradigm. On a side note, the term "limits of knowledge" in the title feels a bit hyperbolic. I always appreciate how Quanta conveys the intricacies of deeply technical topics to a wider audience.
- l33t7332273 3y agoIt’s interesting to think about, but the complexity classes are actually equal[1]. This sort of makes sense if you think of quantum computers as simulatable by a classical computer. [1] https://arxiv.org/abs/2001.04383 https://arxiv.org/abs/2001.04383
- drdeca 3y agoHuh? Assuming I understand your comment correctly, that is, not what that paper is showing. That paper is showing that if the verifier has polynomial time computational power, with two provers who each have unlimited computational power, and who have some shared quantum entanglement, are communicating individually with the prover, and the prover also has access to randomness and such, then there is a protocol that can allow the provers to, for any recursively enumerable language, demonstrate to the verifier, for any string, whether that string is in that language. RE is a WAY bigger class than what the verifier can compute alone. And, is also way bigger than the without-entanglement version, MIP. That paper is showing that adding quantum entanglement to the setup for MIP, allows for way more problems to be in the class.
- l33t7332273 3y ago>RE is a WAY bigger class than what the verifier can compute alone I always think of the RE(CE) sets as those that are possible to compute. I’m aware that RE sets are not computable, but since RE sets are those accepted by a turing machine, I still consider that set to be the “main” one when speaking informally. Maybe this is misguided
- blintz 3y agoIt's exciting that cryptographic constructions (like m/n secret sharing where m is hidden) can solve problems in complexity; I would have expected things to flow mostly the other way.
- mrwnmonm 3y agoWho can read an article this long these days?
- deleted 3y ago[deleted]
- calderknight 3y agoSome people still read entire books (they literally just sit there for hours and read every word on every page)
- mrwnmonm 3y ago[flagged]
- dang 3y agoWe've banned this account for posting unsubstantive and/or flamebait comments and otherwise breaking the site guidelines. You've been doing a bunch of that lately, unfortunately. Not cool. If you don't want to be banned, you're welcome to email hn@ycombinator.com and give us reason to believe that you'll follow the rules in the future. They're here: https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html.
- jdthedisciple 3y agoIkr? I too would rather have the summary of it beamed right into my consciousness in a split second.
- throw_pm23 3y agohttps://libquotes.com/euclid/quote/lby7i8p https://libquotes.com/euclid/quote/lby7i8p
- brabel 3y agoIt interested me, so I did read the whole thing... do you never read anything longer than this at all?? No books? No multi-part blog posts, tutorials?
- inciampati 3y ago[flagged]
- IndySun 3y agorelated : https://www.bbc.co.uk/programmes/b06mtms8 https://www.bbc.co.uk/programmes/b06mtms8 P v NP In Our Time Melvyn Bragg and guests discuss the problem of P versus NP, which has a bearing on online security. There is a $1,000,000 prize on offer from the Clay Mathematical Institute for the first person to come up with a complete solution. At its heart is the question "are there problems for which the answers can be checked by computers, but not found in a reasonable time?" If the answer to that is yes, then P does not equal NP. However, if all answers can be found easily as well as checked, if only we knew how, then P equals NP. The area has intrigued mathematicians and computer scientists since Alan Turing, in 1936, found that it's impossible to decide in general whether an algorithm will run forever on some problems. Resting on P versus NP is the security of all online transactions which are currently encrypted: if it transpires that P=NP, if answers could be found as easily as checked, computers could crack passwords in moments. With Colva Roney-Dougal Reader in Pure Mathematics at the University of St Andrews Timothy Gowers Royal Society Research Professor in Mathematics at the University of Cambridge And Leslie Ann Goldberg Professor of Computer Science and Fellow of St Edmund Hall, University of Oxford