Predictions For 2012
Possibly excepting the last 10 days
Joseph T. Goodman became the owner and editor of a newspaper in Virginia City, Nevada called the Territorial Enterprise, a few years after its founding in 1858. He furthered the circulation of the newspaper throughout the Western territories, and used it as a mouthpiece for positions such as supporting the Union in the Civil War. In his day one could say that this amounted to a prediction. One of his later efforts was to grow grapes in Northern California, and though his own effort seems to have had no memorable yield, one can say he predicted the area would be good for wine.
Today we wish to go over last year’s predictions, and offer a mostly new slate for 2012. The supposed Mayan prediction of the end of the world on December 21st, 2012 makes us hedge by not venturing anything beyond that date.
Goodman’s most lasting work came late in life: he deciphered the notation system used in the Mayan calendar. Juan Martinez-Hernandez and Eric J. Thompson later expanded and confirmed this work, so that the system is now known by their initials GMT—which is neatly suggestive of our own time standard.
As editor as well as owner, Goodman paid attention even to the “Letters” page of his paper. He noticed that one unsuccessful, worldly-wise prospector in Aurora, Nevada, wrote in often with a lively pen. He offered the young man, Samuel Clemens, a job on his paper instead. The stories by Clemens gained enough circulation to earn him a reputation, and today we know him as Mark Twain.
The Mayan Y2K Problem
What Goodman and his followers solved can be abstracted as a constraint-satisfaction puzzle. Most Mayan “long count” inscriptions have five entries in a recognizable tally system, so we’ll call them the coefficients . The questions are what units they multiplied and whether this was radix notation with a single base or multiple bases which we’ll call . The data could be given the form
from cases where the inscription could be sequenced with a historical event whose Gregorian date was known. This could come along with other information conferring similar equations with or approximate equality in place of .
It was clear that the ones place had units of days, and that the Mayans liked to count by or . Thus and , but it was found that , not as in base 20. The switch to base-18 seems surprising but makes closer to a solar year of days. Then (called a katun) and (called a baktun) resumed the base-20 pattern.
The hardest variable to solve was , called the “correlation.” Indeed Goodman, Martinez-Hernandez, and Thompson came up with values apart. Goodman’s value gave a “Day Zero” of August 11 in 3114 BCE, and this was adopted. Thus today’s date (as I, Ken, write, not post date) in Mayan is
Note that the and places are maxed out at , so after more days, the coefficient will tick over.
The issue is whether the base for the place was meant to be base 20 or base 13. If the latter, this is the end my friend. Evidence for the latter is that some Mayan inscriptions indicate more than five places but pad them with 13’s that play the role of zeroes. One noted in Wikipedia’s article here is
whose last five places denote October 19 in the year 744. The inclusion of the leading places, however, grants about 4 billion more years. Another inscription has nineteen leading 13’s. Thereby the Mayans over-predicted the life of the world, as all leading physical theories suggest that at least our branch of the cosmos will freeze or be annihilated long before those places are filled out.
Thus December 21 will end a Mayan cycle of days giving about of our years, but we see nothing more than a limit of 5-place syntax. This is analogous to the two decimal place shortcut that led to the Y2K Problem, in which predicted techno-apocalypse was averted. Well in case we are wrong, at least the 354 days left constitute a lunar year, so we are still offering a year’s worth of predictions.
Reviewing Our 2011 Predictions
Here are the predictions from last year, together with the results.
No circuit lower bound of or better will be proved for SAT.
A Computer Scientist will win a Nobel Prize.
The above are two holdovers from last year. We will let them “ride” and make them again. Note there is no CS Nobel, so what the latter means is that among those cited for science or economics will be someone trained or currently employed in computer science.
The complexity class , bounded-error quantum polynomial time, will be shown to lie in the polynomial hierarchy. This is rather nervy, since contrary to the clear drift of [we cited several recent papers].
Wrong, but some progress has been made—at least we think we have.
A conceptually new algorithm will be discovered for an important practical problem; it will be a breakthrough in asymptotic time but in concrete terms will be even more galactic than previous ones.
Unclear. We would like to claim credit for prognosticating the new bounds on matrix product, but the most we can say is that the jury is still out on whether the algorithms are “conceptually new.”
At least five claims that and five that will be made.
Correct. According to the 13 items numbered 70–82 by this source, there were 7 claims of equal and 7 claims of not equal.
That seems not to add up, but one claimant ‘proved’ it both ways, depending on the presence or absence of certain axioms for reasoning about certain representations of natural numbers.
Graph Isomorphism will be proved to be reducible to the Graph Reconstruction Problem. For background, see this paper.
Apple will invent a new type of alarm clock: the iClock. Pressing the “snooze” button will take you back one hour via your own personal time travel device. It will require a monthly subscription fee and will be wildly successful—however, see this for a caveat.
Does the iPad count?
The world’s population at exactly 12:00am GMT on April will be even.
We think so—but who can prove us wrong?
A “provably” secure crypto-system will be broken.
Of course. Should be disallowed as a prediction, like saying there will be gravity next year.
A Clay problem will be solved by two independent researchers at about the same time.
Some of our new predictions may turn out to exemplify another episode from Joseph Goodman’s life. In 1872 his newpaper opposed William Sharon’s run for the U.S. Senate, Nevada having become a state in 1864. Sharon lost but resolved to try again in 1874. To make sure the paper’s next “prediction” would be to his liking, he bought the paper—and won. That is to say, we hope to promote work on some of our predictions, if we cannot do them ourselves.
Our predictions for the coming year are the following—note that the first two are repeats:
- No circuit lower bound of or better will be proved for SAT.
- A Computer Scientist will win a Nobel Prize.
- Someone other than a Williams will release a headline-making result in November.
- A new set-theoretical relation will be found between one or more of these classes which are all hard for Discrete Log or Factoring (perhaps in a promise-problem form, per this paper) but not known to be hard for :
and one or more of these classes which are -hard (at least under randomized reductions) but not known to be hard for the second level of the polynomial hierarchy:
(All but the last class name is clickable to get its definition at the Complexity Zoo.) We could throw in some other classes for each of these two “regions,” both of which are heavily populated with little knowledge even conditionally. A new binary relation (most likely a new containment) would score a big hit, a new ternary relation a little hit, a new oracle relation we’ll punt.
- Tangible new evidence against the Unique Games Conjecture will be posted (i.e., published at least on the arXiv) by Dec. 21, 2012.
- Tangible new evidence supporting the Unique Games Conjecture will be posted by Dec. 21, 2012.
These last two predictions do not contradict each other. To check whether any published evidence is new or substantial, the Mayan cutoff date allows some pre-holiday time—we hope.
- Tangible new evidence against the Exponential Time Hypothesis will be posted by Dec. 21, 2012.
- Tangible new evidence supporting the Exponential Time Hypothesis will be posted by Dec. 21, 2012.
For a general science bent, we offer:
- The Higgs boson will close the year with a stated confidence above from a single team, but strictly less than from any one team.
- An Earth-sized planet will be detected orbiting within the habitable zone of its single star. (Currently “Earth-sized” and “habitable zone” have been achieved by different exo-planets.)
We’ve thought to add predictions about new conditional lower bounds, improved quasi-randomness properties of simple hash functions, and scalability of quantum computing, but these can come out later and we’ll keep it at 10.
What are your best predictions? We further predict that next year many of our predictions will be wrong.
Happy New Year.
[fixed bases to u,v,w,x,y not v,w,x,y,z; fixed a couple words including “one or more” in prediction 4, which is a less-“nervy” analogue of last year’s prediction about BQP]