7 ms·
The P-versus-NP Page (2016)
- tiborsaas 5y agoQuick stats: [Equal]: 62 [Not equal]: 50 [Undecidable]: 1 [Unprovable]: 2
- deleted 5y ago[deleted]
- kadoban 5y agoIs [Unprovable] the same as [Not equal]? It seems like the only way that's possible is if P!=NP, since in the other case there's just so many proofs available (proofs be example, algos that solve any of several hundred known problems in poly time). So in a sense, any proof that there is no proof would be proof that P!=NP. Maybe I'm missing something?
- jonathanstrange 5y agoI think it means that neither P=NP nor P!=NP is provable.
- kadoban 5y agoBut is it a proof that neither is provable? Or just a statement of giving up? Assuming it's a proof, there's two cases: 1) it's really P=NP, but we can't prove it 2) it's really P!=NP, but we can't prove it If it's case 1, that's impossible. If P=NP, then there exist polytime algorithms for NP-Complete problems, and any of those algorithms are a proof that P=NP. So that's a contradiction. So the _only_ possibility given a proof that it's unprovable would be case 2, thus proving P!=NP and contradicting itself. Am I missing something? Even assuming I'm right, this isn't a proof that one of P=NP or P!=NP are provable, just that it's impossible to prove that neither can be proven.
- lalaithion 5y agoMath proofs start given a set of axioms. The modern set of Axioms are ZFC. If you can find a new axiom A such that ZFC + A is a consistent system[1] and P=NP, and also find a new axiom B such that ZFC + B is a consistent system[1] and P!=NP, then logically, P?=NP cannot have a solution either way in just ZFC. [1] Assuming ZFC is itself consistent
- kadoban 5y agoAre Turing machines representable in ZFC (pretty sure they are)? Seems like it'd be at least _really_ difficult to do that trick if so. That would mean that in ZFC+A there exist algorithms that can't exist in ZFC+B? Hard for me to imagine what those would even be, since they'd have to be representable in ZFC itself anyway, right, since that's all that an algorithm would be this model, a particular Turing machine?
- lalaithion 5y agoYeah, there's a reason most people don't think it's independent. Still, there are a significant number of things that are independent: https://en.wikipedia.org/wiki/List_of_statements_independent_of_ZFC https://en.wikipedia.org/wiki/List_of_statements_independent... But (I think) all of them have to do with infinity in some weird way.
- 12039192301293 5y agoNot sure if this applies here but generally speaking, there are things that are true but unprovable. See Gödel's Incompleteness Theorem [1]. [1] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
- kadoban 5y agoGood callout, thank you. Yeah I'm aware in general that there are unprovable true things. I've somehow convinced myself that this can't be one of them, though the other thread of this I believe I'm being shown how it might be.
- throwaway81523 5y agoNo, it's possible that there is a P-time SAT-solving algorithm A, but that it's not provable that A runs in P-time, and/or it's not provable that A actually solves SAT (even though it does). In fact there is a known and fairly simple algorithm that provably solves SAT, but its running time is unknown. It runs in P-time if and only if P=NP. It is called Levin's Universal Search and you can read about it.
- ColinWright 5y agoI'm assuming that's the stats for the "results" on the linked page. It's certainly not the stats of opinions of mathematicians in my circles.
- dlkf 5y agoLinked on the page is an opinion poll [0] with responses from some prominent mathematicians (including Shor, Conway and Knuth). I thought it was really interesting to hear their thoughts on the problem. [0] http://www.cs.umd.edu/~gasarch/papers/poll.pdf http://www.cs.umd.edu/~gasarch/papers/poll.pdf
- jstx1 5y agoConway didn't care much for it, did he: > (P!=NP) In my opinion this shouldn’t really be a hard problem; it’s just that we came late to this theory, and haven’t yet developed any techniques for proving computations to be hard. Eventually, it will just be a footnote in the books.
- jonathanstrange 5y agoI wrote a German espionage novel about the topic, based on the idea that someone might have found a promising proof of P=NP. However, it got a pretty damning review. Maybe someone with better writing skills should take up the topic?
- Rerarom 5y agohttps://www.goodreads.com/en/book/show/37986693-factor-man https://www.goodreads.com/en/book/show/37986693-factor-man
- einpoklum 5y agoDamning review of your book, or damning review of the proof? ... Anyway, awesome pun!
- jsnell 5y agoWas P=NP just an arbitrary McGuffin, or did the proof actually have plot ramifications?
- jonathanstrange 5y agoNo, not arbitrary. It could have been any other technique or proof that potentially makes breaking ciphers easier, but the idea in the novel is that the proof might have constructive applications or could at least lead to them, and the mathematician who developed it is specialized in the topic and not a crackpot. The decisive factor for the plot is that other agencies want to have it, though.
- shadowgovt 5y agoIt's never said explicitly, but I believe the McGuffin in the movie Sneakers implies its inventor has either found a proof of P=NP or has implemented an algorithm that would imply a proof of P=NP.
- bla3 5y ago> "Proof by contradiction. Assume P=NP. Let y be a proof that P=NP. The proof y can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since P=NP, the proof y can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer scientists to produce a proof), we have a contradiction." Love this :)
- deleted 5y ago[deleted]
- BossingAround 5y agoCan't lose with that argument, eh? :)
- plank 5y agoSorry. Too many experiences to really buy the logic "it can be done, it has not been done, hence contradiction". Indeed e.g. the proof of Fermat's theorem (Wikipedia: After 358 years of effort by mathematicians, the first successful proof was released in 1994 by Andrew Wiles, and formally published in 1995; it was described as a "stunning advance" in the citation for Wiles's Abel Prize award in 2016.) would be a contradiction of that logic. (Indeed, I am very confident that mathematics is a much more developed a mature field then IT). The only time such an argument had been yielded and has some value is in my (not so, I guess) humble opinion when I think Fermi used the argument that if there was a lower energy level of water there surely would have been an animal by now that used this extra energy by converting water to this state (although I cannot find a link to this quite so quickly, so perhaps the argument was slightly different).
- bla3 5y agoIt's a joke, not a proof. I thought it was funny.
- khawkins 5y agoI'm very confident that orders of magnitude more man-hours have been spent thinking about P=NP in the past 20 years than were spent in the whole 358 years on Fermat's theorem. The number of people in academic situations to work on hard problems has increased exponentially. I think it's fair to assume that there are potentially asymptotic limits to what can be achieved, but it's not that we default to one conclusion or the other, but that we conclude that whatever might be the real solution, the complexity of the proof is insurmountable or doesn't exist.
- enriquto 5y agoI like Knuth's take on that matter, saying that P=NP and that it doesn't really matter. The space P is huge and still virtually unexplored. There are extremely powerful algorithms inside O(n^googol), and this is just barely scrapping at the bottom of P.
- deleted 5y ago[deleted]
- malft 5y agoWhy are the examples for P≟NP always so bad? "Solving TSP", "planning airlines better", "get the $1M bounty"? Why not SAT? There's a $200,000 bounty paid out every ten minutes for solutions to a well-known SAT problem. Or crypto. Math. Chess.
- tgv 5y agoChess isn't NP, is it?
- querez 5y ago> There's a $200,000 bounty paid out every ten minutes for solutions to a well-known SAT problem. I'm not sure I follow -- do you mean there is a challenge open somewhere which pays 200k$?
- rrobukef 5y agoBitcoin. Bitcoin relies on SAT being unsolvable.
- 5y ago
- fogof 5y agoThe link to Scott Aaronson’s “Is P vs NP Formally independent” actually points to his broader survey of P vs NP. Here is a link to the one about independence http://people.cs.uchicago.edu/~fortnow/beatcs/column81.pdf http://people.cs.uchicago.edu/~fortnow/beatcs/column81.pdf Both are enjoyable reads.
- mathewsanders 5y agoI’ve tried a few times to understand what P=NP means and never felt like I understand what it’s about. I get that problems can have constant/linear/polynomial/exponential complexity to solve so I (think) I understand ‘P’. Over at NP I get confused around what constitutes a test/validating that a solution is true in polynomial time. For example, a problem, “what’s the shortest path between two points” I get that a brute force breadth-depth first algorithm is going to rapidly take longer as more branches are added, but what constitutes verifying the solution? In that example does verifying a solution mean having access to some prior list of all possible permutations and sorting them to find the shortest path, and because sorting is easy then this is an example of easily verifying?
- Yajirobe 5y agoTo verify the shortest path, you would need to compute all the other paths as well, to be sure. so this doesn't sound like NP-complete
- jcla1 5y agoThis confusion is caused by the different notions of problem: there are "decision" problems and "functional" problems. What grandparent asked ("what is the shortest path?") is a functional problem in nature, whereas P & NP are classes of decision problems. A (more or less) equivalent decision problem version of above question would be "is there a path of length at most X?", which then is of course easy to verify if a potential solution is presented.
- martincmartin 5y agoStrictly speaking, NP problems need to have boolean outcome, so "what's the shortest path" is not an NP problem. Instead, "is there a path with cost <= X?" is an NP problem. Of course, if I had a polynomial-time solver for the "cost <= X?" query, I could easily create a polynomial time solver for the cost of the shortest path, using binary search. See Decision Problem: https://en.wikipedia.org/wiki/Decision_problem https://en.wikipedia.org/wiki/Decision_problem
- jcranmer 5y ago