Review of Behavioral Economics > Vol 3 > Issue 2

On the O’Donnell Algorithm for NP-Complete Problems

N. C. A. da Costa, Advanced Studies Research Group; HCTE; and Fuzzy Sets Laboratory, Mathematical Economics Group, Production Engineering Program COPPE, UFRJ, Brazil, ncacosta@terra.com.br , F. A. Doria, Advanced Studies Research Group; HCTE; and Fuzzy Sets Laboratory, Mathematical Economics Group, Production Engineering Program COPPE, UFRJ, Brazil, fadoria@gmail.com
 
Suggested Citation
N. C. A. da Costa and F. A. Doria (2016), "On the O’Donnell Algorithm for NP-Complete Problems", Review of Behavioral Economics: Vol. 3: No. 2, pp 221-242. http://dx.doi.org/10.1561/105.00000048

Publication Date: 14 Jul 2016
© 2016 N. C. A. da Costa and F. A. Doria
 
Subjects
Economic Theory: Mathematical Economics
 

Share

Download article
In this article:
1. Introduction 
2. Standard and exotic definitions 
3. BGS-like sets 
4. The full counterexample function f: fast-growth property 
5. Exotic BGSF machines 
6. More about the counterexample function 
7. Back to the algorithm 
8. Comments 
9. Almost efficient markets 
10. Conclusion 
References 

Abstract

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

DOI:10.1561/105.00000048