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 ${a_5,a_4,a_3,a_2,a_1}$. The questions are what units they multiplied and whether this was radix notation with a single base or multiple bases which we’ll call ${u,v,w,x,y}$. The data could be given the form

$\displaystyle a_5 v + a_4 w + a_3 x + a_2 y + a_1 z + C > d$

from cases where the inscription could be sequenced with a historical event whose Gregorian date ${d}$ 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 ${z}$ had units of days, and that the Mayans liked to count by ${20}$ or ${13}$. Thus ${z=1}$ and ${y = 20}$, but it was found that ${x = 18 y = 360}$, not ${400}$ as in base 20. The switch to base-18 seems surprising but makes ${x}$ closer to a solar year of days. Then ${w = 20 x = 7,\!200}$ (called a katun) and ${v = 20 w = 144,\!000}$ (called a baktun) resumed the base-20 pattern.

The hardest variable to solve was ${C}$, called the “correlation.” Indeed Goodman, Martinez-Hernandez, and Thompson came up with values ${1}$ 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

$\displaystyle \mbox{January 2, 2012} = 12.19.19.0.6$

Note that the ${w}$ and ${x}$ places are maxed out at ${19}$, so after ${18 \times 20 - 6 = 354}$ more days, the ${a_5}$ coefficient will tick over.

The issue is whether the base ${u}$ for the ${a_5}$ 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

$\displaystyle 13.13.13.13.13.13.13.13.9.15.13.6.9$

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 ${13 \times 144,\!000 = 1,\!872,\!000}$ days giving about ${1,\!872,\!000/365.242 = 5,\!125.369}$ 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.

${\bullet}$ No circuit lower bound of ${ 1000n}$ or better will be proved for SAT.
Fish-in-a-barrel.

${\bullet}$ A Computer Scientist will win a Nobel Prize.
Not yet.

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.

${\bullet}$ The complexity class ${ \mathsf{BQP}}$, 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.

${\bullet}$ 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.”

${\bullet}$ At least five claims that ${ \mathsf{P}=\mathsf{NP}}$ and five that ${ \mathsf{P} \neq \mathsf{NP}}$ 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.

${\bullet}$ Graph Isomorphism will be proved to be reducible to the Graph Reconstruction Problem. For background, see this paper.
Not yet.

${\bullet}$ 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.

${\bullet}$ The world’s population at exactly 12:00am GMT on April ${ 1^{st}}$ will be even.
We think so—but who can prove us wrong?

${\bullet}$ A “provably” secure crypto-system will be broken.
Of course. Should be disallowed as a prediction, like saying there will be gravity next year.

${\bullet}$ A Clay problem will be solved by two independent researchers at about the same time.
Wrong.

## 2012 Predictions

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:

1. No circuit lower bound of ${ 1000n}$ or better will be proved for SAT.

2. A Computer Scientist will win a Nobel Prize.
3. Someone other than a Williams will release a headline-making result in November.
4. 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 ${\mathsf{NP}}$:

and one or more of these classes which are ${\mathsf{NP}}$-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.

5. Tangible new evidence against the Unique Games Conjecture will be posted (i.e., published at least on the arXiv) by Dec. 21, 2012.
6. 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.

7. Tangible new evidence against the Exponential Time Hypothesis will be posted by Dec. 21, 2012.
8. Tangible new evidence supporting the Exponential Time Hypothesis will be posted by Dec. 21, 2012.

For a general science bent, we offer:

9. The Higgs boson will close the year with a stated confidence above ${4\sigma}$ from a single team, but strictly less than ${5\sigma}$ from any one team.

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

## Open Problems

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]

1. January 3, 2012 1:02 am

The blog used to be on Central time—I thought I would still get the Jan 2 date at the top of the post. We can also “predict” some format improvements—neither of us has had time since early summer.

January 3, 2012 11:20 am

Over the break I had the opportunity to visit Toronto and saw an exhibition called “Maya: Their Secrets of the Ancient World” at the Royal Ontario Museum. It was put together by the ROM, the Canadian Museum of Civilization and Mexico’s National Institute of Anthropology and History. If you are planning to be in the Toronto area any time until April 9, I highly recommend that you see it. (It reopens in Gatineau, Quebec, near Ottawa, in May.) One part of the exhibition deals with Mayan time keeping. It makes the point that the Mayan calendar was cyclical. When the cycle runs out, you simply repeat. Your car doesn’t fall apart when the odometer rolls over to 0, after all. (Actually, mine fall apart long before.) If you are planning to go, read Ken’s explanation above carefully. It’s more complete than the explanation provided at the exhibition.

January 3, 2012 4:41 pm

In 2012 Dick will prove that P=NP and Ken will prove that P!=NP… according to whether Cantor’s proof is valid or not. 🙂

4. January 4, 2012 10:12 am

‘A “provably” secure crypto-system will be broken.
Of course. Should be disallowed as a prediction, like saying there will be gravity next year.’

I can’t think of any offhand; can you provide a reference?

• January 4, 2012 11:23 pm

I’m not sure what Dick had in mind when he wrote that part of the post before vac, but we’ve both had in mind the new problems being faced by quantum cryptography, such as at the end of my recent Higgs boson post. The attack referenced there is from 2010, but I think the supplementary attack(s) in these sources at least partly get a 2011 date:

Jan 2011 Nature article
June 2011 PhysicsWorld.com article.
Referring June 2011 note in The Tech Scoop.

Coincidentally, it’s high time I contact one of the authors about a creative translation from Russian which I mostly did years ago and “finalized” in September—but no time.

January 4, 2012 11:16 am

You predict that a computer scientists will win a Nobel Prize in one of the sciences
or economics.

I would love to see a computer scientist win the Nobel Prize for Peace or Literature.

I predict that won’t happen in 2012, but someday.

• January 4, 2012 11:26 pm

Perhaps Tim Berners-Lee and other genitors of the Internet—specifically its openness as a contribution to world peace?

January 5, 2012 9:32 am

Bertrand Russell did it already …

• January 5, 2012 10:15 am

Hajduk’s post leads us to reflect that (at least) six STEM-trained professionals have already won Nobel Prizes in Peace or Literature: Borlaug, Fo, Pauling, Russell, Sakharov, and Solzhenitsyn (very likely there are more than six, and if so, who are they?).

As for STEM organizations that are Peace Prize winners, these include the IPCC, the IPPNW, and the Pugwash Conferences.

These examples suggest (implicitly) at least three credibly strong computer science candidates for a Nobel Peace Prize: Richard Stallman, Linus Torvalds, and the GNU Software Foundation.

To be sure, none are theorem-provers, but on the other hand, there’s more to computer science, peace, and literature than theorem-proving, eh?

My vote would go to Richard Stallman, whose Nobel Address surely would be passionate and memorable. Also, I’m curious to see how Stallman would dress for the occasion. 🙂

• January 5, 2012 12:14 pm

PS: according to Wikipedia:

When asked about his influences, [Richard Stallman] replied that he admires Mahatma Gandhi, Martin Luther King, Jr., Nelson Mandela, Aung San Suu Kyi, Ralph Nader, and Dennis Kucinich,

Of the Stallman Six, there are three Peace Prize winners (King, Mandela, Kyi); moreover in the year of Gandhi’s assassination no Peace Price was awarded, “there being no suitable candidate”, and finally, both Nader and Kucinich are prominent and effective peace advocates.

This six-for-six correlation can hardly be accidental — Stallman too is a conscious worker for peace.

This being the case, what I posted above (with an admixture of humor) deserves to be stated more seriously, plainly, and respectfully: Richard Stallman’s personal philosophy and lifetime achievements in computer science are entirely deserving of a Nobel Peace Prize nomination.

January 4, 2012 11:02 pm

Bill: It will be Knuth, for that classic of young adult literature, “Surreal Numbers”.

7. January 5, 2012 8:25 am

The seven immortal mathematicians of last week’s GLL poll (Euclid, Euler, Gauss, Gödel, von Neumann, Newton, Turing … does “immortal” equate to unary-name recognition?) all earned their reputations not only by solving classic problems, but (possibly to an even greater extent) by posing new classes of wonderfully interesting problems.

So what new classes of mathematical problems will become recognized in 2012 as wonderfully interesting?

Without being sure what constitutes a witness extraction procedure, this class of mathematical problems is very interesting (to me) — and yet witness extraction is a topic sufficiently novel that there is as yet (apparently) no Wikipedia page discussing it.

What other mathematical topics / problems / challenges are sufficiently novel that they (as yet) have no Wikipedia page, and yet are sufficiently interesting and mathematically natural that (hopefully) Wikipedia entries for them are likely to be created in the year 2012?

Witness extraction is my concrete mathematical wiki-prediction for 2012: what is yours?

January 5, 2012 6:04 pm

Thanks for advertising the French logic school. You could even make your prediction true by creating the page. 🙂 My own prediction is that the “P versus NP problem” wiki page – which exists in 21 languages as of today – will be created in at least one more language in 2012.

January 5, 2012 6:15 pm

… actually it does exist in 22 languages as yet – I forgot to count the current language.

January 5, 2012 12:46 pm

My wish for GLL in 2012 is that it features more technical posts as it did in its earlier wonderful days.

• January 7, 2012 5:16 pm

Sounds like Santa didn’t bring you a Red Ryder BB gun.

January 7, 2012 10:29 am

Nobel peace prize should go to Wikipedia or Google for allowing us to look things up