The Expected Complexity of Problem Solving


Authors
Kevin Kelly
Carnegie Mellon University
Abstract
Worst case complexity analyses of algorithms are sometimes held to be less informative about the real difficulty of computation than are expected complexity analyses. We show that the two most common representations of problem solving in cognitive science each admit aigorithms that have constant expected complexity, and for one of these representations we obtain constant expected complexity bounds under a variety of probability measures.
Keywords No keywords specified (fix it)
Categories No categories specified
(categorize this paper)
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 41,507
External links

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.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Complexity Theories, Social Theory, and the Question of Social Complexity.Peter Stewart - 2001 - Philosophy of the Social Sciences 31 (3):323-360.
Is Multi-Tasking Complex?W. Bentley MacLeod - 1998 - Behavioral and Brain Sciences 21 (6):840-841.
Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Physical Complexity and Cognitive Evolution.Peter Jedlicka - 2007 - In Carlos Gershenson, Diederik Aerts & Bruce Edmonds (eds.), Worldviews, Science, and Us: Philosophy and Complexity. World Scientific. pp. 221--231.
Complexity: From Formal Analysis to Final Action.Douglas Frye & Philip David Zelazo - 1998 - Behavioral and Brain Sciences 21 (6):836-837.
Philosophy of Chemistry and Limits of Complexity.Hrvoj Vančik - 2003 - Foundations of Chemistry 5 (3):237-247.

Analytics

Added to PP index
2010-12-22

Total views
14 ( #559,684 of 2,248,650 )

Recent downloads (6 months)
1 ( #1,031,479 of 2,248,650 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature