14
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 6
    $\begingroup$ More appropriate to cs.stackexchange. $\endgroup$
    – Yuval Filmus
    Commented Nov 20, 2012 at 23:31
  • 2
    $\begingroup$ How about E or EXP? $\endgroup$
    – Yuval Filmus
    Commented Nov 20, 2012 at 23:39
  • 5
    $\begingroup$ @YuvalFilmus really ? This seems like an interesting question to me and not trivial at all $\endgroup$
    – Suresh Venkat
    Commented Nov 21, 2012 at 0:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Nov 21, 2012 at 0:31
  • 5
    $\begingroup$ 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] $\endgroup$
    – Ryan Williams
    Commented Nov 21, 2012 at 7:17

1 Answer 1

Reset to default
21
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Love the warning! :) $\endgroup$
    – Tayfun Pay
    Commented Nov 22, 2012 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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