# Alternate notion of complexity based on gap between brute-force and the best algorithm?

Typically, efficient algorithms have a polynomial runtime and an exponentially-large solution space. This means that the problem must be easy in two senses: first, the problem can be solved in a polynomial number of steps, and second, the solution space must be very structured because the runtime is only polylogarithmic in the number of possible solutions.

However, sometimes these two notions diverge, and a problem is easy only in the first sense. For instance, a common technique in approximation algorithms and parameterized complexity is (roughly) to prove that the solution space can actually be restricted to a much smaller size than the naive definition and then use brute-force to find the best answer in this restricted space. If we can a priori restrict ourselves to, say, n^3 possible answers, but we still need to check each one, then in some sense such problems are still "hard" in that there's no better algorithm than brute-force.

Conversely, if we have a problem with a doubly-exponential number of possible answers, but we can solve it in only exponential time, then I'd like to say that such a problem is "easy" ("structured" may be a better word) since runtime is only log of the solution space size.

Does anyone know of any papers that consider something like hardness based on the gap between an efficient algorithm and brute-force or hardness relative to the size of the solution space?

One problem with formalizing the question is that the phrase "solution space for Problem A" is not well-defined. The definition of a solution space needs a verifier algorithm which, given an instance and a candidate solution, verifies whether or not the solution is correct. Then, the solution space of an instance wrt to a verifier is the set of candidate solutions that make the verifier output "correct".

For example, take the problem SAT0: given a Boolean formula, is it satisfied by the all-zeroes assignment? This problem is trivially in polynomial time, but its solution space can vary wildly, depending on which verifier you use. If your verifier ignores the candidate solution and just checks if all-zeroes works on the instance, then the "solution space" for any SAT0 instance on that verifier is trivial: it is all possible solutions. If your verifier checks to see if the candidate solution is a satisfying assignment, then the solution space of a SAT0 instance can actually be quite complex, arguably as complex as any SAT instance's solution space.

That said, the problem of "avoiding brute-force search" can be formalized in the following way (as seen in the paper "Improving exhaustive search implies superpolynomial lower bounds"). You are given a verifier algorithm that runs in time $t(n,k)$, on instances of size $n$ and candidate solutions of $k$ bits. The question is, *on arbitrary instances of size $n$, can we determine if there is a correct solution (wrt this verifier) with at most $k$ bits, in much less than $O(2^k t(n,k))$ time?

Note $O(2^k t(n,k))$ is the cost of trying all strings of length up to k, and running the verifier. So the above can be seen as asking whether we can improve on brute-force search for the given verifier. The area of "exact algorithms for NP-hard problems" can be seen as a long-term effort to study the difficulty of improving on brute-force search for certain very natural verifiers: e.g. the question of finding better-than-$2^n$ algorithms for SAT is the question of whether we can always improve over brute-force search for the verifier that checks if the given candidate solution is a satisfying assignment to the given SAT instance.

The paper shows some interesting consequences of improving on brute-force search for some problems. Even improving on brute-force search for "polynomial-size solution spaces" would have interesting consequences.

• Since Ryan is too modest to link to his own papers :), here's the link: cs.cmu.edu/~ryanw/improved-algs-lbs2.pdf also, Ryan, latex is working now, so you can use $..$ to mark off the math in your post. – Suresh Venkat Aug 22 '10 at 20:06
• I am more than a bit reluctant to reference my own papers in an answer. But when it fits the question exactly, it's hard to resist... – Ryan Williams Aug 22 '10 at 22:36

How would you deal with typical dynamic programming problems ? Here, what often happens is that the space of optimal solutions is polynomially bounded, but the space of solutions isn't. So it seems "easy" in your sense because the running time is logarithmic in the solution space, but it's "hard" in your sense because it runs "brute force" over all potentially optimal solutions.

• There are a number of subtleties in definitions that would need to be worked out, like exactly what algorithms qualify as brute force. I would probably try restrict the solution space as follows: if, for a given problem size, you can remove an answer from consideration without looking at the data then it's not in the solution space (admittedly, this allows multiple distinct solution spaces). That said, I would be happy with an answer that is similar in spirit to my question even if it differs in many details. – Ian Aug 19 '10 at 22:09

The perspective seems to assume some things, like fininitude of solution spaces.

For example, think about the problem of generating a Voronoi tesselation from a set of input points. Here there is an infinitely sized solution space as each point in the edges of the diagram is a tuple of real numbers. Yet a solution can be reached in O(n log(n)) in the number of input points (for the plane).

• True, some problems may not fit in this framework. Although for some problems with real number outputs one may be able to make the space finite by describing the output algebraically in terms of the inputs (e.g. as linear combinations of input points). I don't know much about geometric algorithms, where real numbers are typically encountered, so I'm not sure how often or whether this would be possible. – Ian Aug 19 '10 at 22:15
• Real numbers aren't the only way to get infinite solution spaces. Consider a game between Alice and Bob. Alice picks an integer n. Bob makes guesses, and Alice tells him if he is higher, lower or equal to her secret n. Bob has a finite time strategy for finding n because it is always finite. He starts a 0 and then picks a large constant c. Alice tells him which direction her n is in and Bob will guess c^turn until he finds a lower and upper bound, where he performs a binary search for n. Then again I suppose you could argue that there is a finite solution space in the number of bits of n... – Ross Snider Aug 19 '10 at 22:32

Related are problems that admit algorithms with polynomial delay. The first solution, and every solution thereafter, can be generated in polynomial time. Johnson, Yannakakis, and Papdimitriou discuss this framework in the context of other possible gaps (such as polynomial total time): On Generating All Maximal Independent Sets, Information Processing Letters 27, 119–123, 1988.