P ≠ NP Provable in PA | Hacker News Reader

P ≠ NP Provable in PA

arxiv.org

17 pointsdanielam23 comments

Ad 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 is withdrawn and 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".

This should probably have a "(2020)" in the title.

Also, I agree with the 8yo comment here: 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.

(revised 2021-03-09, v10.)

For 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_ab...

2. https://en.wikipedia.org/wiki/Peano_axioms

I usually see it refer to Peano Arithmetic

I 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

Papers 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.

No, 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.

Forget 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.

It'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.

> 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?

No, because that's not disseminated to a broader community. If it were, I'm going to link a standardized reference document that defines the terms, like they do in RFCs.

Edit: Actually, even with such an "internal" document, my preference would be to overexplain rather than underexplain, and define an acronym (or neologism I had learn myself recently) before using it. REST is a special case though, in that defining out the acronym doesn't actually help explain how people use it.

> 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.

Actually, jargon does reduce cognitive load; that's why all specialized communities have it to make fine distinctions that are relevant in the community more concisely and precisely than less specialized language does.

Nobody's going to take you by the hand every time you want to read something above you.

Have some humility.

Part of the problem is that so much mathematics is named after people, and not something more descriptive like the EFA above.

We should stop naming maths after people.

Note 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.

I 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 and https://math.stackexchange.com/a/213264.

Does 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.

Okay, I'll bite. PA probably isn't Pennsylvania, so what is it?

Peano 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.

No 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.

If I had read that comment just a few seconds earlier, you would probably owe me a new keyboard now. ;-)

what is PA?

Peano Arithmetic

Reply on news.ycombinator.com