25 June 1985
L.N. Trefethen hereby bets Peter Alfeld that by December 31, 1994, a method will have been found to solve Ax=b (n x n linear system of eqs) in O(n**(2+epsilon)) operations for any epsilon > 0. Numerical Stability is not required.The winner gets $100.- from the loser. signed: Peter Alfeld, Lloyd N. Trefethen Witnesses: Per Erik Koch, S.P. Norsett.
Norsett added the note (This is an A-stable problem) .
Nick paid up in February 1996. We renewed the bet for another 10 years, and another $100 will change hands on January 1, 2006. On February 13, 1996, we amended the bet as follows: If one of the contestants settles the matter prior to January 1, 2006 (by Peter Alfeld showing that no O(n^2) method exists, or Nick Trefethen constructing an O(n^2) method) the loser will pay the winner $200 at that time.
The best known exponent for linear algebra problems is currently 2.376, thanks to an algorithm due to Coppersmith and Winograd in 1987.[16-Aug-1996]