View source for Computational foundations for attentive processes

==Capacity limits and computational complexity==
One of the most frustrating things about studying attention is that research is so often
accompanied by vague discussions of capacity limits, bottlenecks, and resource limits.
How can these notions be made more concrete? The area of computer science known as
Computational Complexity is concerned with the theoretical issues dealing with the cost of
achieving solutions to problems in terms of time, memory and processing power as a
function of problem size. It thus provides the necessary theoretical foundation on which to
base an answer to the capacity question.

It is reasonable to ask whether computational complexity has relevance for real problems.
[[#Stockmeyer88|Stockmeyer & Chandra (1988)]] present a compelling argument. The most powerful
computer that could conceivably be built could not be larger than the known universe,
could not consist of hardware smaller than the proton, and could not transmit information
faster than the speed of light. Such a computer could consist of at most <math>10^{126}</math> pieces of
hardware. It can be proved that, regardless of the ingenuity of its design and the
sophistication of its program, this ideal computer would take at least 20 billion years to
solve certain mathematical problems that are known to be solvable in principle (for
example, the well-known traveling salesman problem with a sufficiently large number of
destinations). Since the universe is probably less than 20 billion years old, it seems safe to
say that such problems defy computation<sup>1</sup>. There exist many real problems for which
this argument applies (see [[#Garey79|Garey & Johnson, 1979]], for a catalog), and they form the
foundation for the theorems presented here.

With respect to neurobiology, many have considered complexity constraints in the past but
mostly with coarse, counting arguments (for example, [[#Feldman82|Feldman & Ballard 1982]] or [[#Tsotsos87|Tsotsos
1987]]). All roads lead to the same conclusions: the brain cannot fully process all stimuli in
parallel in the observed response times. But this is like saying there is a capacity limit: This
does not constrain a solution. By arguing in this manner we are no closer to knowing what
exactly the brain is doing to solve this problem. This paper takes the position that a more
formal analysis of vision at the appropriate level of abstraction will help to reveal
quantitative constraints on visual architectures and processing. First, however, it is
important to address the applicability of this analysis for the neurobiology of the brain.

# This claim, plus the entire discussion of intractability, relies on the current unproved conjecture that the space of problems that fall into the category referred to by Stockmeyer and Chandra is not the same as the space of problems that are efficiently solvable. Formally, we assume P≠NP, and one normally needs to acknowledge this.