Complexity class associated with exhaustive search

What is the complexity class associated with exhaustive search algorithms? (if there is one)

Is it NP or PSPACE?

Are there restricted models of computation capturing the class of exhaustive search algorithms similar to models for greedy and dynamic programming?

-
More appropriate to cs.stackexchange. –  Yuval Filmus Nov 20 '12 at 23:31
How about E or EXP? –  Yuval Filmus Nov 20 '12 at 23:39
@YuvalFilmus really ? This seems like an interesting question to me and not trivial at all –  Suresh Venkat Nov 21 '12 at 0:30
The various local search classes start with a problem space where a solution is guaranteed to exist, and the challenge is to search the space in subexponential time. It might be related. –  Suresh Venkat Nov 21 '12 at 0:31
It's a little vague but I like the question. I wrote a paper about it a long time ago. Maybe this will help the Anonymous questioner: stanford.edu/~rrwill/bfsearch-rev.ps [WARNING: It's likely that I disagree with almost all of the opinions stated there, it was written 10 years ago] –  Ryan Williams Nov 21 '12 at 7:17

Here's a summary. Informally, if you do not keep any scratch work from previous trials, and just try all possible solutions in lexicographical order until a desired solution is found, then brute force corresponds precisely to $P^{NP}$. If you keep around even $3$ bits of scratch work from one possible solution to the next, then you can do $PSPACE$, via Barrington's theorem. There are other possibilities, such as what happens when you don't run in lex order but according to some other efficiently computable list of all strings.