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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.