Tuesday, March 15, 2022

Problem X won't be solved in MY lifetime- but what about...

1) In 1989 on the episde The Royale of Star Trek: The Next Generation (which takes place in the far future)  Captain Picard is working on Fermat's last theorem which he says quite explicitly is still open.

When I saw the episode I asked Larry Washington, a Number Theorist at Univ of MD, when he thought FLT would be solved. He said

                                      It will be solved within the next 10 years.

And indeed- Wiles solved it in 1993-sort of. There was a flaw in the proof which he fixed in 1994 with the help of his former student Richard Taylor. Wiles published the correction to the flaw in 1995, so we will date it as having been solved in 1995. Larry Washington was correct.  And in an episode of Star Trek: Deep Space Nine in 1995 (episode name:Facets) Dax says that a previous host, Tobin Dax, had done the most creative work on FLT since Wiles. Maybe Tobin wrote this limerick:

A challenge for many long ages

Had baffled the savants and sages

Yet at last came the light

Seems that Fermat was right

To the margin add 200 pages.


I asked Larry W when he thought Riemann would be solved. He said  

                    In your lifetime but not in mine.

He is about 10 years older than I am and I think we are both in good health. This seems like a rather precise prediction so I am skeptical. But he did get FLT right...

2) In class I sometimes say things like 

I do not think Quantum Computers will factor faster than classical in my lifetime. 

I do not think P vs NP will be solved in my lifetime.

I can imagine P=BPP will be proven in my lifetime. (I said that 10 years ago. I am less imaginative now.) 

I hope the muffin problem is solved in my lifetime (it was, see here).

I didn't quite think about the difference in my age and the students until recently when I was working with Ilya Hajiaghayi (Mohammd H's 9 year old son) on cryptography and he said 

In your recorded lecture you said you don't think quantum computers will be a threat to cryptography  in your lifetime. What about in my lifetime?

Indeed- his lifetime and mine are rather far apart. 

I am reminded that one of the answers to my P vs NP poll made the point that while we have some sense of what will happen in the next 10 years, maybe even 20, math and life can change so much that conjectures beyond that are guesswork. Any  prediction for x years from now you should have confidence < 1/ln(x) of it being true.





6 comments:

  1. Why Riemann and P=BPP in your lifetime but not P=NP?

    ReplyDelete
  2. There has been steady progress on RH over the years. However, When Larry Washington said it I think there had been some progress recently. But yes, it seems to have died down.

    Same with P=BPP: There has been some progress on this, but it seems to have stopped.

    For P=NP I have seen no progress.

    But of course, who knows! Here is hoping that just to prove me wrong you solve P vs NP!

    ReplyDelete
  3. Regarding RH, if you are inclined to believe Deligne's proof for analog as progress you might be wrong. There is no Frobenius in the context of original RH. Why should same proof work? It may very well be the whole community has been fooling itself. For P=BPP I wonder if any of the false proofs attempted so for in the context of NP not in P/poly might work for E not in i.o.P/poly? Any thoughts why known strategies cannot work?

    ReplyDelete
  4. ^^It seems pretty ridiculous to me to think that "false proofs attempted so far" have anything interesting to say here... are you familiar with many examples of such false proofs (I assume you're referring to crank P = NP proofs for example) which did lead to other interesting ideas?

    ReplyDelete
    Replies
    1. I had a blog post where I say that the false proofs that resolve P vs NP have rarely lead to anything interesting:

      https://blog.computationalcomplexity.org/2015/03/has-anything-interesting-every-come-out.html

      Delete
  5. You never know. Reputed people have tried to publish false proofs. They might contain new ideas even if they are wrong.

    ReplyDelete