A Computable Economistï¿½s Perspective on Computational Complexity
K. Vela Velupillai ()
No 723, Department of Economics Working Papers from Department of Economics, University of Trento, Italia
A computable economist.s view of the world of computational complexity theory is described. This means the model of computation underpinning theories of computational complexity plays a central role. The emergence of computational complexity theories from diverse traditions is emphasised. The unifications that emerged in the modern era was codified by means of the notions of efficiency of computations, non-deterministic computations, completeness, reducibility and verifiability - all three of the latter concepts had their origins on what may be called "Post's Program of Research for Higher Recursion Theory". Approximations, computations and constructions are also emphasised. The recent real model of computation as a basis for studying computational complexity in the domain of the reals is also presented and discussed, albeit critically. A brief sceptical section on algorithmic complexity theory is included in an appendix.
New Economics Papers: this item is included in nep-cbe, nep-cmp and nep-hpe
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8) Track citations by RSS feed
Downloads: (external link)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://www.unitn.it/files/23_07_velupillai.pdf [301 Moved Permanently]--> https://www.unitn.it/files/23_07_velupillai.pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:trn:utwpde:0723
Access Statistics for this paper
More papers in Department of Economics Working Papers from Department of Economics, University of Trento, Italia Contact information at EDIRC.
Bibliographic data for series maintained by Luciano Andreozzi ().