On the O’Donnell Algorithm for NP -Complete Problems
Newton C. A. da Costa, Francisco Antônio Dória · Review of Behavioral Economics · 2016
We present and discuss the O’Donnell 1979 algorithm for the solution of NP-complete problems. If P < NP is proved in a theory with greater “provability strength” than Primitive Recursive Arithmetic, the O’Donnell algorithm turns out to be almost polynomial. We elaborate on how close to polynomial it might be. As an application, we show that follows from Maymin’s theorem on efficient markets that, given our metamathematical condition above, there are “almost efficient” markets (that is to say, markets where information about their operation is known in almost polynomial time).