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

Abstract: 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.

Date: 2007
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)

Downloads: (external link)
http://www.unitn.it/files/23_07_velupillai.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 403 Forbidden

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

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