Complexity of finding new solutions beyond known lists explained
The Complexity of Finding Additional Solutions
Computational Complexity
Summary
Finding additional solutions to a problem after some solutions are already known can be more complicated than just finding the first one. The authors show how the difficulty of getting new solutions depends on the number of solutions you already have and certain technical conditions. They also find cases where finding any fixed number of new solutions is easy, but finding an unlimited number is as hard as some of the toughest search problems in computer science. This work helps clarify how solution-finding complexity changes as the list of known solutions grows.
What this means in practice
- •For algorithm designers: Understand limitations in designing algorithms that find new solutions beyond a known set under polynomial-time constraints.
- •For software verification teams: Identify when extending solution lists for problems may become computationally infeasible based on solution count and complexity theory.
A theory result. No direct application yet.
Authors
Saman Farhat
Abstract
We study the difficulty of finding a new solution when a list of distinct solutions is already supplied. For any fixed finite collection of list lengths, we can prescribe the additional-solution degrees while preserving a given $1$-paddable domain and first-solution degree. We also prove an exact compatibility condition for prescribing an arbitrary positive-list degree at the same time: it must dominate every prescribed fixed-level degree, and this condition suffices. All degrees use polynomial-time reductions with at most one oracle query and correct behavior on empty fibers; the realization needs no assumption about P versus NP. The combined construction gives each underlying witness exponentially many short counter copies. A list that exhausts these copies is long enough to pay for exhaustive search through the underlying witness bound. Separately, we construct a total problem whose first-solution task and every fixed-length additional-solution task are polynomial-time solvable, while its arbitrary-list task is FNP-complete. Assuming P differs from NP, the domain, first degree, and entire fixed-level degree sequence therefore do not determine the arbitrary-list degree. A constant fiber cap restores determination by finitely many fixed levels. The constructions change witness sets and do not prescribe an infinite sequence of degrees or enumerate all remaining solutions.