The Complexity of Computing Second Solutions

We study the complexity of computing a second solution for an NP search problem when we are given a first solution. NP search problems (or search problems for short) are a fundamental concept in complexity theory, first studied as multivalued functions by Selman [13, 14, 15] and further developed by Fenner et al. [6, 5] and Hemaspaandra et al. [10]. Particularly intensive research has been done on the class of total search problems TFNP [12], where each input is guaranteed to have at least one solution (see [7] for an overview). While the standard setting of search problems asks to compute a first solution, we focus on computing a second solution. This means we are given a problem instance $x$ together with a valid solution $y$, and have to find another valid solution $y^{\prime }$. In particular, we are interested in the extent to which a first solution helps compute a second one.

On the one hand, our investigation is motivated by use cases where users ask for multiple options to choose from (e. g., routes or schedules), or for new solutions different from the previous ones (e. g., generation of exam tasks). On the other hand, the following consideration shows that our investigation is also interesting from a theoretical perspective: It is easy to devise examples where finding an additional solution is simple (because it can be easily derived from a first solution, e. g., reversing the direction of a Hamiltonian cycle). In contrast, for other examples, finding the first few solutions is trivial, but finding additional solutions is hard (e. g., when searching for divisors). This observation prompts us to systematically investigate the relationship between first and second solutions from a complexity theory perspective.

In the past, questions about the complexity of finding alternative solutions were mostly raised in custom-tailored form for concrete problems, like the “Another Hamiltonian Cycle” problem (see [3] for an overview). Ueda and Nagao [16] consider several specific problems of this shape and employ the general problem scheme “alternative solution for $X$” based on an intuitive understanding of the base problem $X$. They investigate the resulting problem for several such problems $X$ (e. g., 3-Dimensional matching and Nonogram).

In our paper, we use the following generic and abstract definition of finding an $n$-th solution, which was proposed by Yato and Seta [17] and which is applicable to any search problem: given the solutions $y_1,\mathrm{\dots },y_{n-1}$ for the input instance $x$, we have to find a new $n$-th solution $y_n$ (if such solution exists). This definition yields, for any search problem $A$, the unique corresponding second solution problem $A_{[1]}$.

We analyze how the formulation of a problem influences the complexity of computing second solutions. Our main result in Section 4 shows that this complexity is completely determined by the choice of the type of solution, but independent of the underlying decision problem.

In 4.11, we show that for any nonempty search problems $A$ and $B$ (representing two arbitrary degrees of difficulty), there exists a search problem $C$ such that:

1. 1.

   $C$ is as difficult as $A$.

2. 2.

   $C_{[1]}$ is as difficult as $B$.

This shows that the complexity of $C$ is independent of the complexity of its second solution problem $C_{[1]}$. Here, “independent” really is to be understood in a mathematical sense: the complexity of one problem variant provides no information about the complexity of the other. For example, there exists a search problem $C$ just as hard as factorization such that its second solution problem is just as hard as graph isomorphism.

Conclusion 2 uses the additional assumption 1-paddable, which is weaker than paddablitity in the sense of Berman-Hartmanis [2]; hence, natural problems in NP are 1-paddable. The conclusion is based on the following arguments. By 4.8, for every 1-paddable $X\in \text{NP}$ and every nonempty search problem $B$, there exists a search problem $C$ such that:

1. 1.

   $\text{dom}(C)=X$.

2. 2.

   $C_{[1]}$ is as difficult as $B$.

Hence, $C$ solves the decision problem $X$, while its second solution problem $C_{[1]}$ has the same complexity as $B$. Phrased in terms of machines (cf. 4.7), we construct an NP machine for $X$ such that finding a second accepting path has the same complexity as $B$. Since any such choice of complexity is possible, we recognize that each 1-paddable $X\in \text{NP}$ has maximum freedom for the complexity of the second solution problem. As a consequence, the choice of the type of solution has the greatest possible influence on the difficulty of the second solution problem. For example, for the satisfiability problem SAT, there exist search problems $C$ and $D$ both solving SAT such that the second solution problem of $C$ is just as hard as factorization, while that of $D$ is solvable in polynomial time. This demonstrates that NP decision problems have no intrinsic complexity w. r .t. the search for a second solution. Rather, the specification of the type of solution (that is, the corresponding search problem) determines the complexity of computing a second solution, where all levels of complexities are possible. Note that, given $\text{P}\ne \text{NP}$, the analog statement for first solution problems does not hold: under this assumption, there does not exist a search problem $D^{\prime }$ such that $\text{dom}(D^{\prime })=\text{SAT}$ and $D^{\prime }$ is solvable in polynomial time.

4.12 restates this result in terms of degree structures, as follows. For every 1-paddable $X\in \text{NP}$, all of the following classes share the same degree structure:

• $\mathrm{■}$

  FNP

• $\mathrm{■}$

  $\{A_{[1]}\mid A\in \text{FNP}\}$

• $\mathrm{■}$

  $\{A_{[1]}\mid A\in \text{FNP}\text{ and }\text{dom}(A)=X\}$

This shows that the entire variety of degrees of difficulty in FNP reappears in second solution problems; this still applies even if we restrict to any single 1-paddable $X\in \text{NP}$ and corresponding second solution problems.

In our proofs, we use artificially defined search problems to achieve the desired degrees of difficulty. Therefore, we do not obtain statements about specific problems. We rather see our results as an objective description and systematic fine-grained analysis of the empirical observation that the difficulty of computing second solutions strongly depends on the formulation of the problem, more precisely the chosen type of solution.

We choose Turing machines (as commonly defined) as the computation model for our algorithms, usually on the fixed alphabet $\mathrm{\Sigma }≔\{0,1\}$. Let $\text{ran}(f)$ denote the range of $f$.

In the following, when defining a deterministic polynomial-time algorithm by means of a function definition, we can informally use “$\perp$” as a function value instead of “$n.d.$”, which other algorithms can use to continue their computations. For this, we define $x\cdot \perp ≔\perp \cdot x≔\perp$ for a compact notation in our formulas.

Each multivalued function is a function problem that poses the task of algorithmically computing any of its function values for a given input. From any function problem, we can always derive a decision problem that poses the question whether an instance has at least one function value:

Hence, $f$ belongs to FNP if and only if its graph belongs to P and the length of function values is polynomially bounded. Each $f\in \text{FNP}$, which we refer to as a search problem, uniquely defines its corresponding decision problem $\text{dom}(f)\in \text{NP}$. The class FNP is sometimes also referred to as ${\text{NPMV}}_g$.

Note that from $B={\mathrm{\Sigma }}^{\ast }\wedge A{\le }_m^{p}B$, it follows that $A={\mathrm{\Sigma }}^{\ast }$. For function problems, a different kind of reduction is needed: intuitively, a function problem $f$ reduces to $g$ if an efficient algorithm for $g$ would allow us to solve $f$ efficiently as well. This is captured by the following notion, similar to a metric reduction [11]: on input $x$, a polynomial-time algorithm must find a value $z\in f(x)$; we allow it one oracle query $y$ for a value $z^{\prime }\in g(y)$. The notation $M^O$ shall express which oracle $O$ an oracle algorithm $M$ can access.

Note that $f{\le }_{1\text{-}T}^{p}g$ implies $f{\le }_T^{p}g$, where ${\le }_T^p$ denotes polynomial-time Turing reduction with an unbounded number of queries. Therefore, our results also hold for ${\le }_T^p$ instead of ${\le }_{1\text{-}T}^p$. In our proofs, we will show ${\le }_{1\text{-}T}^p$ by defining a function or an oracle algorithm from which it is obvious that it can be computed in polynomial time and behaves correctly for each matching oracle. For this, we will informally use $g^{\ast }(x)$ as a return value of an arbitrary refinement $g^{\prime }(x)$, i. e. as an answer to the oracle query $x$.

From any search problem $A$, we denote the class of equally difficult problems (by our reduction term ${\le }_{1\text{-}T}^p$) as its degree $\mathrm{deg}(A):=\{A^{\prime }\mid A^{\prime }{\equiv }_{1\text{-}T}^{p}A\}$. Furthermore, we define the degree structure of a complexity class $𝒞$ to be the set of all its degrees, i. e. $\{\mathrm{deg}(A)\mid A\in 𝒞\}$. We consider two complexity classes $𝒞$ and $𝒟$ to share a degree structure (w. r. t. ${\le }_{1\text{-}T}^p$) if both classes contain at least one element of every degree that appears in any of the two classes, i. e. if $\{\mathrm{deg}(A)\mid A\in 𝒞\}=\{\mathrm{deg}(A)\mid A\in 𝒟\}$ holds.

We now define a formalism that describes the search for an additional solution. For this, we define the function problem where an instance of $f$ together with $n$ solutions are given as a list encoding, and the task is to find an $n+1$-th solution. For a given $f$ and $n$, this search problem is uniquely defined. An input is only valid if it contains $n$ valid and pairwise distinct solutions, and we ask the answer to be valid and different from all solutions that are already part of the input. Invalid inputs shall not have function values. Let $⟨\cdot ⟩$ denote an appropriate list encoding, and let $\epsilon$ denote the empty word.

Compared to the definition of $f_{[n]}$, the definition of $f_{[n]t}$ provides invalid inputs with one trivial and unique solution. Generally, it holds that $f_{[n]},f_{[n]t}\in \text{FNP}$. Additionally, it holds that if the existence of $n$ solutions in $f$ implies the existence of an $n+1$-th solution, $f_{[n]t}\in \text{TFNP}$.

Function problems are useful for describing the search for accepting paths in nondeterministic machines. Our motivation for drawing a parallel between the two concepts is that we will allow ourselves to treat function problems and nondeterministic machines as formally different, but intuitively synonymous. For reasoning the similarity, we define a corresponding function problem for each nondeterministic machine.

For an NP machine $M$, it holds that $f_M\in \text{FNP}$; the function problem’s associated task is the search for accepting paths in this specific machine. Conversely, for each FNP problem $f$, we can immediately derive a nondeterministic machine that tests one of the possible function values of $f(x)$ on each of its paths on input $x$.

Note that despite $f_{M_g}\ne g$, it holds that $f_{M_g}{\equiv }_{1\text{-}T}^{p}g$.

In the proof of the main theorem, we will want to add a special behavior to many of the positive instances of one of the two sets that the construction works on. To know when we can safely apply our special behavior, we will need a subset of positive instances that are both easy to find and easy to recognize. Formally, we want an infinite subset, decidable in polynomial time, whose elements are indexed such that the bijection from index to element is easy to compute in both directions. We call sets that have such a subset 1-paddable. We will justify this choice of name shortly.

If $A$ is 1-paddable via $p$, the desired infinite subset is $\text{ran}(p)$; in other words, $p(x)\in A$ holds for all $x$. The index of a given $y\in \text{ran}(p)$ is determined by the polynomial-time computable term $x=p^{-1}(y)$. From index $x$, it is easy to return to $y$ via $y=p(x)$. Since the output of $p^{-1}(x)$ tells us whether $x\in \text{ran}(p)$, it holds that $\text{ran}(p)\in \text{P}$.

Let “$A{\le }_{1,i}^{p}B$” denote that there exists a total, injective, polynomial-time computable and polynomial-time-invertible function $f$ such that $x\in A\iff f(x)\in B$. With this reduction term, we obtain an alternative definition of 1-paddability:

To avoid having to show 1-paddability individually for each set, we want to utilize known results for paddability, which is defined as follows.

Almost all discovered NP-complete problems are known to be paddable. We show all these problems to be 1-paddable as well.

Obviously, there are function problems $f\in \text{FNP}$ such that $\text{dom}(f)$ is not 1-paddable. However, we can demonstrate that there exists at least one function problem $f^{\prime }$ in each FNP degree such that $\text{dom}(f^{\prime })$ is 1-paddable. In other words, we can fix the difficulty of an arbitrary FNP problem $f$ that this $f^{\prime }$ will assume.

We start with two problems $A,B\in \text{FNP}$; we must also add the requirement that $\text{dom}(A)$ is 1-paddable via $p$ such that we have $\text{ran}(p)$ as a set of easily decidable instances to work on. To better understand the construction, we will work not directly with function problems, but with corresponding decision machines that guess one of the solutions on each path, as discussed in Section 2.3. In this way, when referring to $A$ and $B$, we are actually referring to the machines $M_A$ and $M_B$ from now on. The result of our efforts will be a new (intermediary) machine $\alpha$ such that the corresponding function problem $f_{\alpha }$ works towards the design goals outlined above. (The problem of finding a second solution in this function problem corresponds to finding a second path in machine $\alpha$.)

We must tackle the following task in constructing $\alpha$: the reduction “$B\le 2^{\text{nd}}$ solution in $\alpha$” must solve a problem $B(x)$ when allowed access to one answer to a “second solution” (or “second accepting path”) problem in $\alpha$, which we call ${\alpha }_{[1]}$ in our notation. How can such a reduction algorithm pose an “${\alpha }_{[1]}$ query” that helps it solve its “$B$ question”? To be able to ask for a second accepting path, it must already provide a first accepting path itself.

To solve this challenge, we make use of the 1-padding function $p$ that separates $\text{dom}(A)$ into instances $\text{ran}(p)$ that are easy to decide, and a rest $\text{dom}(A)\setminus \text{ran}(p)$ which contains all difficult instances. We will make use of the former to precisely reach the complexity of $B$ with ${\alpha }_{[1]}$.

We show that the constructed problem generally has a solution if and only if $A$ has a solution. Furthermore, we show that finding a first solution is equally difficult as solving $A$, and that finding a second solution (or deciding whether such exists) is equally difficult as solving $B$ (or as deciding whether $B$ has a solution, respectively).

The case $B\in \text{TFNP}$ grants us the interesting additional property that, given a first solution, finding a second solution in the constructed problem is a total search problem itself (except for invalid inputs).

How can we apply the results from Theorem 4.6 if we are only given two function problems $A$ and $B$, but do not know $\text{dom}(A)$ to be 1-paddable? By applying 3.6, we can still reach a weakened conclusion.

We obtain the following statements, which are formalized by 4.12:

• $\mathrm{■}$

  The set of all second solution problems has the same degrees as the entire class FNP.

• $\mathrm{■}$

  This holds even if we restrict to second solution problems of search problems that correspond to a single 1-paddable $X\in \text{NP}$.

• $\mathrm{■}$

  Alternatively, we can restrict to second solution problems of search problems that assume an arbitrary difficulty $A\in \text{FNP}$.

The last statement implies that in every FNP degree, one can find a problem that matches an arbitrary difficulty $B\in \text{FNP}$ for its second solution.