<p>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: </p>

<p><a href="http://stanford.edu/~rrwill/bfsearch-rev.ps">Brute Force Search and Oracle-Based Computation</a> </p>

<p>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.</p>

<p>[<strong><em>WARNING WARNING WARNING:</em></strong> <em>It's likely that I disagree with almost all opinions stated in this paper. It was written about 10 years ago, by someone with the same name but who is essentially a different person.</em>]</p>

CC BY-SA 3.0
2012-11-22T02:30:13.903Z
Love the warning! :)
Tayfun Pay
CC BY-SA 3.0
2012-11-21T19:31:53.937Z
2012-11-21T19:31:53.937Z
Ryan Williams
<p>What is the complexity class associated with exhaustive search algorithms? (if there is one)</p>

<p>Is it NP or PSPACE?</p>

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

CC BY-SA 3.0
2012-11-20T23:31:10.800Z
More appropriate to cs.stackexchange.
Yuval Filmus
CC BY-SA 3.0
2012-11-20T23:39:01.733Z
How about E or EXP?
Yuval Filmus
CC BY-SA 3.0
2012-11-21T00:30:03.720Z
@YuvalFilmus really ? This seems like an interesting question to me and not trivial at all
Suresh Venkat
CC BY-SA 3.0
2012-11-21T00:31:16.697Z
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
CC BY-SA 3.0
2012-11-21T05:03:53.100Z
i do not completely understand. complexity classes include problems not algorithms. is the point to define a complexity class of problems for which the optimal algorithm is exhaustive search?
Sasho Nikolov
CC BY-SA 3.0
2012-11-21T07:17:51.983Z
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: http://www.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
CC BY-SA 3.0
2012-11-21T07:26:11.130Z
@SashoNikolov PPP is the class of problems where you search for a solution whose existence is guaranteed by the pigeonhole principle. PLS captures problems where the algorithm "looks like" gradient descent. Indeed, for all of these classes (including PPAD), the class was designed to capture a certain kind of heuristic algorithm.
Suresh Venkat
CC BY-SA 3.0
2012-11-21T08:17:28.587Z
@SureshVenkat i thought those are classes where an inefficient argument (be it pigeonhole, or parity) proves that a solution always exists. i am not sure what the appropriate analogy is - maybe the class of problems solvable by brute-force search. for that ryan's paper seems very relevant.
Sasho Nikolov
CC BY-SA 3.0
2012-11-21T17:01:19.550Z
@RyanWilliams: Repost as an answer? I was going to post something about perebor, and how NP was designed to capture it (cf. Trakhtenbrot's survey), but that in some cases natural brute force search algorithms (e.g. for winning strategies) lead to PSPACE. But your paper very nicely covers this, and also gives a single model in which both $P^{NP}$ and $PSPACE$ pop out as natural characterizations of perebor under two slightly different conditions.
Joshua Grochow
<cc.complexity-theory><ds.algorithms><reference-request><big-picture><machine-models>
Complexity class associated with exhaustive search
Anonymous
# Complexity class associated with exhaustive search

(Asked by: username_0 on 2012-11-20)

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?

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, big-picture, machine-models
> **Comments:**
> **username_1**: More appropriate to cs.stackexchange.  
> **username_1**: How about E or EXP?  
> **username_2**: @YuvalFilmus really ? This seems like an interesting question to me and not trivial at all  
> **username_2**: 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.  
> **username_3**: i do not completely understand. complexity classes include problems not algorithms. is the point to define a complexity class of problems for which the optimal algorithm is exhaustive search?  
> **username_4**: 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: http://www.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]  
> **username_2**: @SashoNikolov PPP is the class of problems where you search for a solution whose existence is guaranteed by the pigeonhole principle. PLS captures problems where the algorithm "looks like" gradient descent. Indeed, for all of these classes (including PPAD), the class was designed to capture a certain kind of heuristic algorithm.  
> **username_3**: @SureshVenkat i thought those are classes where an inefficient argument (be it pigeonhole, or parity) proves that a solution always exists. i am not sure what the appropriate analogy is - maybe the class of problems solvable by brute-force search. for that ryan's paper seems very relevant.  
> **username_5**: @RyanWilliams: Repost as an answer? I was going to post something about perebor, and how NP was designed to capture it (cf. Trakhtenbrot's survey), but that in some cases natural brute force search algorithms (e.g. for winning strategies) lead to PSPACE. But your paper very nicely covers this, and also gives a single model in which both $P^{NP}$ and $PSPACE$ pop out as natural characterizations of perebor under two slightly different conditions.  

---

## 1 answers

### Answer by username_4 on 2012-11-21. Score: 21

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:

[Brute Force Search and Oracle-Based Computation](http://stanford.edu/~rrwill/bfsearch-rev.ps)

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.

[***WARNING WARNING WARNING:*** *It's likely that I disagree with almost all opinions stated in this paper. It was written about 10 years ago, by someone with the same name but who is essentially a different person.*]

> **Comments:**
> **username_6**: Love the warning! :)  

---

