Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
5  
More appropriate to cs.stackexchange. –  Yuval Filmus Nov 20 '12 at 23:31
2  
How about E or EXP? –  Yuval Filmus Nov 20 '12 at 23:39
5  
@YuvalFilmus really ? This seems like an interesting question to me and not trivial at all –  Suresh Venkat Nov 21 '12 at 0:30
1  
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
5  
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
show 4 more comments

1 Answer

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

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.]

share|improve this answer
1  
Love the warning! :) –  Tayfun Pay Nov 22 '12 at 2:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.