10 ms·
P ≠ NP Provable in PA
- Igelau 6y agoOkay, I'll bite. PA probably isn't Pennsylvania, so what is it?
- Jtsummers 6y agoPeano Arithmetic if my googling is correct. That was my guess but it would be nice of the paper authors to be courteous to readers. Even if they’re more familiar with the domain than us, there’s no guarantee an acronym is unique within the domain. Technical writing 101.
- rossdavidh 6y agoNo no, that's the thing. It's not necessarily provable in, say, California or Texas, but we now know that P ≠ NP in at least one state, so it's a pretty significant step forward. Previous work using induction shows that if it's true in one state, it is true in any other state. This still does leave places like D.C. and Puerto Rico as open questions as well, of course.
- krylon 6y agoIf I had read that comment just a few seconds earlier, you would probably owe me a new keyboard now. ;-)
- jitl 6y agowhat is PA?
- omni- 6y agoPeano Arithmetic
- sujayakar 6y agoNote that this paper was first submitted to arXiv in May 2020. I haven't been able to find any previous discussion by an expert, though.
- vghaisas 6y agoI didn't know and I'm sure others are wondering too: PA probably means Peano Arithmetic. See https://en.m.wikipedia.org/wiki/Peano_axioms https://en.m.wikipedia.org/wiki/Peano_axioms and https://math.stackexchange.com/a/213264 https://math.stackexchange.com/a/213264.
- nonameiguess 6y agoI don't know why the authors can't define any of these, but the complete mapping of capital letter soup to actual words is: PA: Peano Arithmetic EFA: Elementary Function Arithmetic ZFC: Zermelo-Frankel set theoretic axioms plus the axiom of Choice
- airhead969 6y agoPapers should have a glossary or define terms inline with parentheses: Yet Another Acronym (YAA). It's annoying to jargonify, paper or not, because it doesn't help reduce the cognitive load of the reader and it makes the paper less accessible.
- tablespoon 6y agoNo, not really. The intended audience for a paper like this is not a layman who needs a glossary, but a fellow expert fluent in the field's jargon.
- airhead969 6y agoForget the "layman" elitist snobbery. There are people from adjacent fields and people in other fields who read such papers. Furthermore, that merely reinforces the "Latinization" of fields rather than making knowledge reasonably-accessible to all who wish to read it. In addition, prepress processing such a paper could easily add a glossary of term and/or hyperlinks mechanically.
- tablespoon 6y agoIt's not snobbery, but an acknowledgement that jargon exists for a reason, and that reason isn't to make the writing opaque to outsiders. You're probably a software engineer. Are you going to write out REST (REpresentational State Transfer) in every design document you put up on your company wiki for your team that describes one, just in case a non software engineer wants to read it? Are you going to explain the concept? No, you're going to write for your audience, and stuff like will get their way. If you want to read infra-disciplinary writing, you need to be willing to do the work to familiarize yourself with the concepts and terms of the discipline that you don't understand, instead of expecting everyone, always, to offer close-at-hand definitions just in case. That latter expectation is only reasonable for writing targeted at a general audience.
- TimSchumann 6y agoFor anyone wondering what PA stands for, after a few minutes digging I came across a subsection of this P versus NP Wikipedia Article [1] which lead to this article about Peano Axioms[2]. My guess would be it stands for Peano Axioms or Peano Arithmetic, which is a formalized system of reasoning about natural numbers -- if I understand the first couple sentences of the Wikipedia article. 1. https://en.wikipedia.org/wiki/P_versus_NP_problem#Results_about_difficulty_of_proof https://en.wikipedia.org/wiki/P_versus_NP_problem#Results_ab... 2. https://en.wikipedia.org/wiki/Peano_axioms https://en.wikipedia.org/wiki/Peano_axioms
- monstersinF 6y agoI usually see it refer to Peano Arithmetic
- asymptosis 6y agoThis should probably have a "(2020)" in the title. Also, I agree with the 8yo comment here: https://news.ycombinator.com/item?id=5785787 https://news.ycombinator.com/item?id=5785787 > ArXiv has many "proofs" that P=NP and that P!=NP. ArXiv does not do any vetting of correctness (it is beyond their scope.) We don't need a HN submission for this and the title is inaccurate/clickbait.
- tunesmith 6y ago(revised 2021-03-09, v10.)
- chx 6y agoAd hominem attacks, especially in mathematics should not stand but still I would give a heads up to laypeople: be very very cautious about just accepting this until further reviews are done because this is not the first time he submitted a paper with absolutely bombastic results which has been proven flawed. https://arxiv.org/abs/1712.09678 https://arxiv.org/abs/1712.09678 is withdrawn and https://arxiv.org/abs/1812.03837 https://arxiv.org/abs/1812.03837 is still being revised and from what I read about the latter the chances of it being salvaged is very low. Here's one of the easiest to understand comments about it: > I have attempted to read through the paper, and there are several places where it states that construction can be done, and provides evidence that the construction can be done, but never outright does the construction. It then rapidly devolves into higher mathematics which the author later acknowledged with "Thanks. That does seem like a good objection".
- xtiansimon 6y agoDoes anyone have a suggestion of a more engaging explanation of P != NP, its history and significance for the neophyte reader of popular math/sci subjects? On the lines of, Aczel, Amir D. The Mystery of the Aleph: Mathematics, the Kabbalah, and the Search for Infinity (2001) or whatever.