Pseudoscientists in the Intelligent Design (ID) movement have long desired a track record of ID-related publications in peer-reviewed journals. Now Dembski and Marks are touting a new publication as a step in this direction. Reading the paper will be a disappointment to everyone who had hoped for any non-trivial results. The three things offered are:
(a) A simplistic notion of a search problem as consisting of nothing else than a search space and a target set .
(b) Definition of the endogenous probability as the probability of encountering a point in the target set using using uniformly random sampling. E.g. after search space queries, . Also introduced is the exogenous probability that a search algorithm will sample a point from the target set in at most queries. The ratio
measures how well suited the search algorithm is to the search problem, and is interpreted as a measure of how much problem-specific knowledge is incorporated in the search algorithm.
(c) Calculations of and for a few examples of search problems.
That’s it. Dembski and Marks do not discuss how the target set might arise or be chosen, simply assuming that it is as constant as the search space. For a search problem to be in any way interesting and significant there must be some more structure available than just a set and a subset . Clearly, a target set might arise in many ways and in many settings it is necessary to consider a probabilistic model for both target set-membership and target set size rather than a constant target set. For example, in the Traveling Salesman Problem one considers a class of several problem instances, with different target sets, and attempts to find algorithms that work for well on average or even in the worst-case scenario. When searching a database, the size of the target set depends on the database query and on the content of the database. A good algorithm for database search works for several different target sets. The approach taken by Dembski and Marks suffers from the flaw that entirely structureless search problems are uninteresting and lack significance, and these properties carry over to their analysis of search problems.
W. Dembski and J. Marks II. Conservation of Information in Search: Measuring the Cost of Success. IEEE Trans. Sys. Man. Cybernetics A 39:1051 (2009)