David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Studia Logica 56 (3):427 - 454 (1996)
This paper deals with a philosophical question that arises within the theory of computational complexity: how to understand the notion of INTRINSIC complexity or difficulty, as opposed to notions of difficulty that depend on the particular computational model used. The paper uses ideas from Blum's abstract approach to complexity theory to develop an extensional approach to this question. Among other things, it shows how such an approach gives detailed confirmation of the view that subrecursive hierarchies tend to rank functions in terms of their intrinsic, and not just their model-dependent, difficulty, and it shows how the approach allows us to model the idea that intrinsic difficulty is a fuzzy concept.
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Julia Tanner (2007). Intrinsic Value and the Argument From Regress. Forum Philosophicum 12 (2):313-322..
Stanley S. Wainer (1999). Accessible Recursive Functions. Bulletin of Symbolic Logic 5 (3):367-388.
Dan Marshall (2009). Can 'Intrinsic' Be Defined Using Only Broadly Logical Notions? Philosophy and Phenomenological Research 78 (3):646-672.
Arto Salomaa (1985). Computation and Automata. Cambridge University Press.
T. L. S. Sprigge (1984). Non-Human Rights: An Idealist Perspective. Inquiry 27 (1-4):439 – 461.
V. Hoffmann-Kolss (2010). Denby on the Distinction Between Intrinsic and Extrinsic Properties. Mind 119 (475):763-772.
Stephen E. Newstead, Peter Bradon, Simon J. Handley, Ian Dennis & Jonathan St B. T. Evans (2006). Predicting the Difficulty of Complex Logical Reasoning Problems. Thinking and Reasoning 12 (1):62 – 90.
Bruce Edmonds (2000). Complexity and Scientific Modelling. Foundations of Science 5 (3):379-390.
Sanjay Jain & Arun Sharma (1997). The Structure of Intrinsic Complexity of Learning. Journal of Symbolic Logic 62 (4):1187-1201.
Added to index2009-01-28
Total downloads5 ( #234,982 of 1,100,092 )
Recent downloads (6 months)2 ( #190,012 of 1,100,092 )
How can I increase my downloads?