### Monday February 11, 2002

**Speaker**: Martin Cohn

**Title**: The Complexity of a Vision Model

**Abstract**: Dan Graboi and John Lisman (Brandeis Biology) describe a
computational model of how the human vision system recognizes words.
Their experiments found that a greedy algorithm worked best.

I'll discuss their model and show that the greedy algorithm is not optimal,
but that the problem as posed is NP-complete, so that an optimal strategy
is (almost certainly) not feasible. On the other hand, the problem is
approximable by the very algorithm they suggest, and any better
approximation can be proved to be NP-hard.