kasku.net/blog/2022/11/23

Collatz Conjecture, P vs NP, Anonymous Wiseguys

Jeffrey C. Lagarias's The 3x+1 Problem: An Overview is something I came across when I searched "collatz" into arXiv to try and find some "proofs", one of which began the final proof with the following:

Proof. For any positive integer n > 1, it is an independent event with equally probability for n is an even number or n is an odd number. [...]

which I thought was pretty funny.

Anyway, if this sounds interesting to you:

This paper aims to address two questions:

  1. What can mathematics currently say about this problem?
  2. How can this problem be hard, when it is so easy to state?

To address the first question, this overview discusses the history of work on the problem. Then it describes generalizations of the problem, and lists the different fields of mathematics on which the problem impinges. It gives a brief summary of the current strongest results on the problem.

then I'd recommend having a look at the overview. It's interesting to see the history of the attitudes to the problem.

Speaking of unsolved problems, this time P vs NP, William I. Gasarch wrote an article in 2002 where he asked various theorists when and how they thought the problem would be resolved, called "The P=?NP Poll" [PDF]. It turns out he also revisited this topic in 2012, in the imaginatively named "The Second P=?NP Poll" [PDF] and again in 2019, in "The Third P=?NP Poll" [PDF]. But after all, there's not really much point in doing those polls when there is this simple and obvious solution to the problem, which fits in 506 bytes.

Once again it's interesting to see people's attitudes, especially the kind of meta-narrative ideas that come up, saying things about the place of the problem in the structure of time, or even societal differences. Of course, we can't forget the "anonymous wiseguys".

For example in the 2002 poll:

John Conway: (Princeton University, Math, 2030, P≠NP, Conversion to some arithmetized form of the Berry Paradox) 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.

Carl Smith: (University of Maryland, 2025, model-dependent, novel diagonalization) Before the Berlin wall fell I had thought it would be solved by a young eastern block mathematician who didn't have to worry about tenure and could hence spend his best years thinking about P≠NP for hours, days, weeks, months, years, decades, until he either solved it or became an old Eastern block mathematician. Now that the Berlin wall has fallen, the number of young mathematicians who can afford to not worry about tenure and just think deep thoughts has fallen so it may be longer then it would have been to solve it. In any case, the solution will not be as enlightening as the problem has been.

Anonymous3: (Names, schools, dates changed to protect the innocent) On Dec 14, 1991 it was shown that P=NP by undergraduate Mary Lou Koslowsky on her Algorithms final exam at The University of Southern North Dakota. Her ingenious but somewhat hastily written proof, establishing that 3-SAT could be reduced to 2SAT in O(n3) time, received only 2 points of credit out of a possible 25 and the comment "Wrong." She left computer science and became a pharmacist, working now at Osco Drugs in Lake Wobogon, where all problems have above average complexity.

and from the 2019 poll, square brackets are editor's notes from the original:

Anonymous: The day after I die. And due to that answer, I'll answer the question about printing my name "No", since otherwise, if anyone is so utterly unwise as to believe my "when" answer, it will be open season on me... eek! [On the one hand, I have respected your wishes and not revealed your name. On the other hand, I know your name. And I really want to know the answer...]

Don Knuth: I can’t wait for people to realize that P=?NP is only a question about the existence of a polynomial time algorithm, not about the knowledge of one. We already know, for example, that there exists a polynomial time algorithm to decide membership in any given minor-closed graph family; but we don't really know how to decide it, except for a few actual families.