Studia Logica 56 (3):427 - 454 (1996)
|Abstract||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)|
|Through your library||Configure|
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 downloads3 ( #212,976 of 722,700 )
Recent downloads (6 months)1 ( #60,006 of 722,700 )
How can I increase my downloads?