Favorite Theorems of the Next Ten Years
The best way to predict the future is to create it—Abraham Lincoln
|
| 2016 memorial by David Bailey |
Jonathan Borwein passed away a few years ago. He had been one of the top experts on 
Today we talk about the hardness of predicting mathematical and computational advances.
Borwein wrote a wonderful article on the future of mathematics. It was titled “The Future of Mathematics: 1965 to 2065” and was written for the 2015 centenary of the MAA, midway in his range of time.
Thus, his article looked forward by first looking backward at what would have been looking forward back then.
Prediction is Hard
Borwein talks about predicting the future and how hard it is. He does this by listing a few predictions that were not correct:
- “Radio has no future. Heavier than air flying machines are impossible. X-rays will prove to be a hoax.” — William Thomson (Lord Kelvin), English physicist and inventor, 1899.
- “This telephone has too many shortcomings to be seriously considered as a means of communication. The device is inherently of no value to us.” — Western Union internal memo, 1876.
- “Folks, the Mac platform is through— totally.” — John Dvorak, PC Magazine, 1998.
- “The problem with television is that people must sit and keep their eyes glued on a screen; the average American family hasn’t time for it.”— New York Times, 1949.
- “Where … the ENIAC is equipped with 18,000 vacuum tubes and weights 30 tons, computers in the future may have only 1,000 vacuum tubes and weigh only 1.5 tons.” — Popular Mechanics, 1949.
Ken’s favorites are ones that have long been technologically feasible but never became economical. An example is that in 1959, Arthur Summerfield—then US Postmaster General—predicted that in a a few years, bulk canisters of air mail would be sent across oceans in hours by intercontinental missile. This was said without any inkling of e-mail. And whereas e-mail is “non-physical,” our physical packages arrive no faster than 60 years ago—indeed slower with this year’s supply-chain issues at Pacific ports.
Why Are Predictions Hard?
One reason the future is hard to predict is that we tend to make predictions that are too conservative. For example: replace the last prediction by:
“Where … the ENIAC is equipped with 18,000 vacuum tubes and weights 30 tons, computers in the future may weigh one pound.”
The trouble is people would have laughed at this as ridiculous. How could 30 tons be reduced to a single pound? Indeed.
Of course today people are talking about computers that weight almost nothing and can flow through your bloodstream. See nanobots.
A year ago, we covered a paper and slides by Kevin Buzzard titled, “The future of mathematics?” His third slide embeds a hint on what makes prediction hard:
The key is what he says about AI advances coming in a phase change. A phase change is different from a bolt-from-the-blue. Before the change, the situation seems to be one that is well understood to be progressing slowly. Then a year passes, and boom. Again what happens is that predictions that seemed to be well-founded are exposed as too conservative.
Understanding how this supplements the bolt-from-the-blue kind of event leads to the conclusion:
The future is whippy.
And that is why predictions are hard.
Some Predictions
Nevertheless, we wish to make a few predictions ourselves:
-
The P versus NP problem will be solved by the following date: 2032
years. We make no prediction which way it is resolved. (This is squarely within the 2030-to-2040 range that Ken gave in 2002 in Bill Gasarch’s first P=NP poll.)
-
We do not believe that factoring and graph isomorphism will be resolved in the same period: 2032
- Quantum computers will be able to factor all numbers up to one million purely via Peter Shor’s algorithm by 2030. This may not seem impressive—and it isn’t—but compare what Wikipedia summarizes about the past decade here.
- The Bitcoin protocol will be broken in at most five years. This will have a huge impact of course on the real markets.
- A super-linear lower bound on Boolean complexity will be found for some concrete problem.
Open Problems
We predict that we will be way off. Completely wrong. That sounds safe. What do you think?
Ken adds that his impression from holiday shopping in Barnes and Noble is that the pandemic has been productive for books. How much so for research? When will we be able to say?
Is there any prediction on when people (the scientists/mathematicias) will start to become more open-minded?
The first two predictions seem slightly in disagreement, since if P=NP the second is resolved.
I noticed in the poll that I predicted that P vs NP would be solved in 2036, so I am in agreement with Ken.
In March 13, 2012 researches demonstrate that we can communicate using neutrinos.
“Beams of neutrinos have been proposed as a vehicle for communications under unusual circumstances, such as direct point-to-point global communication, communication with submarines, secure communications and interstellar communication. We report on the performance of a low-rate communications link established using the NUMI beam line and the MINERVA detector at Fermilab. The link achieved a decoded data rate of 0.1 bits/sec with a bit error rate of 1% over a distance of 1.035 km, including 240 m of earth.”
I think the Riemann hypothesis will be solved in the next few years. Moreover, this might be proved by the Robin or Nicolas Criterion. In fact, Jean-Louis Nicolas has made a new huge step forward on the Robin inequality in August 3, 2021.
I have tried to focus in that direction as well. My home page is:
https://uh-cu.academia.edu/FrankVega
Look at these peer-review answers that I have received this year about my work:
“There is novelty in this paper, and the paper is probably publishable, however, in my opinion it does not meet the high … standards” (Rejected)
or
“In particular, it seems like this paper builds on existing techniques to expand the number of cases where the inequality is known to hold. While this is good to know and deserves to be published, to reach the level of … one needs fundamentally new techniques or needs to handle a significantly larger class of numbers; for example if infinitely many distinct primes were done that would be a much stronger result.” (Rejected)
Conclusions: Sometimes proving partially or completely RH is not pretty good enough!!!
https://inquiryintoinquiry.com/2013/04/01/the-present-is-big-with-the-future/
Notice that predicting the future is (seems) as hard as predicting the output of a blackbox algorithm based on a portion of its past computation … 🙂
1) In the movie 2001: A Space Odyssey had a pan-am flight going into space. With Bezos and others going into space we may see something like this- but Pan Am is out of business.
2) I predicted that the prediction market INTRADE would to badly on picking who would be the Vice Presidential candidate (see
https://blog.computationalcomplexity.org/2008/09/i-would-be-on-intrade-that-intrade-will.html
)
I did not predict that intrade would go out of business.
3) You say the predictions are too conservative. But it can also go the other way around:
Where is my jetpack?
Heck, where’s our blimp docks!?
Dear Richard Lipton,
Dear Lance,
The following was posted to Lance and Bill. It certainly relates to you.
You should have mentioned that the Clay Mathematics Institute has voted unanimously:”No Confidence to ALL mathematics journals”. This is one of the remarkable decisions in the history of mathematics. Why did they revamp their rules, entirely? What is the rationale? It’s worth discussion, isn’t?
The social constructivists view of philosophy of mathematics it is like the:”English Common Law”. Below is an illustration comparing SAT and Factoring. Obviously they are incomparable, incompatible. The former is about “True” and “False”,while the later is about numbers. The EXISTENCE of both is a different EXISTENCE.
If you ask me what’s the difference between both existence(s), the answer is:”A dress which is tailored of 26 letters (the English language) must be lacking. Or, as Billy Ocean said in his song (Suddenly):”When a thousand words are not enough to say what I feel inside”.
Even Renes Descartes, the founder of Modern thought, Le Fondateur de la Pensee Moderne” told them:”I think, therefore, I am” (Je Pense, donc je suis”. This happened when he doubted everything, absolutely everything, he doubted his own existence. At the end, he realized that he MAY NOT doubt the fact that he is doubting. Hence:”I think, therefore, I am”.
He concluded that he made his own existence (the motivation to drink water, or the motivation to run away from a lion), he made his existence a PROPERTY of his doubt!
While doubting should have been a PROPERTY of his own (denied) Existence.
I leave it for you to extrapolate this about the existence of numbers vs. the existence of Truth and Falsity.
Below are some thoughts that was sent to your earlier thread.
Best,
Rafee Kamouna.
================================================
SAT is a logical problem, while factoring is a mathematical problem. Mixing both types MUST lead to a contradiction. This was trivially observed by the ancients even before Aristotle. The ancients had the following Philosophy Levels:
Integer Factoring never involves a notion of truth.
I sent to you both Bill and Lance copies of My P vs. NP Claim which was sent to the CMI President as well as all Scientific Advisory Board members.
Just input any paradox in any language (Formal, or Natural), the Cook-Levin theorem collapses. I re-state it
\forall w\in L\in NP \exists M(w)=SAT iff M accepts w
Take the meaning of w to be any paradox, you will never be able to reduce it to SAT. Please try it by pencil and paper.
It’s impossible tell the sun to leave the sky.
It’s impossible to ask a baby not to cry.
Can the ocean,
Keep from rushing to the shore,
It’s impossible. Courtesy of Perry Como
I’m sure that Lance remembers that he refereed my 2008 JACM paper and 2009 ACM ToCT while Bill was the Complexity Theory area editor of JCSS, when its Managing editor refused to revise the 2 papers. Then declined the decision and asked me to select reviewers. I selected (Great Cook and Great Karp), then the Managing editor declined again.
Enter the following as an input, then tell me what happens to the Cook-Levin:
1. Thanks God, I’m an atheist.
2. No for insulting the Idiot president.
3. This sentence contains letters more than itself.
4. The penalty that scored the goal before reaching the goal.
Richard Lipton calls these sentences: “Self-Defeating Sentences”. When it comes to any of the paradoxes in my papers, he must avoid them.
Deolalikar’s proof (11 years old) was an opportunity for him while mine is a threat.
Best,
Rafee Kamouna.