The search for a search: Measuring the information cost of higher level search

Abstract

Many searches are needle-in-the-haystack problems, looking for small targets in large spaces. In such cases, blind search stands no hope of success. Success, instead, requires an assisted search. But whence the assistance required for a search to be successful? To pose the question this way suggests that successful searches do not emerge spontaneously but need themselves to be discovered via a search. The question then naturally arises whether such a higher-level “search for a search” is any easier than the original search. We prove two results: (1) The Horizontal No Free Lunch Theorem, which shows that average relative performance of searches never exceeds unassisted or blind searches. (2) The Vertical No Free Lunch Theorem, which shows that the difficulty of searching for a successful search increases exponentially compared to the difficulty of the original search.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,069

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

  • Only published works are available at libraries.

Analytics

Added to PP
2009-01-28

Downloads
3 (#1,728,901)

6 months
0

Historical graph of downloads
How can I increase my downloads?

Citations of this work

On Mathematical Anti-Evolutionism.Jason Rosenhouse - 2016 - Science & Education 25 (1-2):95-114.

Add more citations

References found in this work

No references found.

Add more references