depth first search

In a previous post I was a bit inaccurate when trying to make a point about the kinds of complexity issues that arise when dealing with practical problems in AI. I stated that human vision accomplished object recognition using constant depth circuits. Memory plays a role in object recognition, so characterizing the human process of object recognition as constant depth may be wrong. In any event, the function that adults apply in recognizing objects is really quite remarkable both in terms of speed and accuracy. Of course you probably wouldn’t realize this unless you spent any time trying to get computers to do similar feats.

The complexity issue that is normally studied in AI is not the complexity of the object recognition function itself (in the brain or in computers), but the difficulty finding the appropriate function. Treated this way, there are a number of models of complexity (e.g. probably approximately correct) that apply to the problem of finding functions that do things like identify objects.

My understanding is that the best computer vision object detectors (e.g. histograms of oriented gradients) can be learned in polynomial time. That said, there are other problems in vision that are known to be NP-complete, so even in this rather applied problem area, we can’t really escape the fundamental problems and concerns of complexity theory.

•