<p>The question seems to be solved while I was writing this answer, but let me post my answer anyway.</p>

<p>Yato and Seta [YS03] (both are my colleagues when I was a student) propose a general framework to prove the NP-completeness of this kind of problems, where they are called Another Solution Problems or ASPs, and prove the NP-completeness of the ASPs of many puzzles.  They consider a restricted notion of reductions between relation problems called ASP reductions, and show that the NP-hardness of ASPs is preserved under ASP reductions and show that many known reductions can be in fact viewed as or modified to ASP reductions between natural relation problems.</p>

<p>[YS03] Takayuki Yato and Takahiro Seta.  Complexity and completeness of finding another solution and its application to puzzles.  <em>IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences</em>, E86-A(5):1052–1060, May 2003.</p>

CC BY-SA 2.5
2010-12-06T00:01:01.517Z
I know someone who is considering this as a possible direction for a PhD thesis, and we talked about it briefly, though I know nothing about the area.  It doesn't seem as though there's been much followup since the paper you cite, though perhaps my search skills are weak.  Are you aware of any significant papers since 2003?
Aaron Sterling
CC BY-SA 2.5
2010-12-06T00:25:12.863Z
@Aaron: There are other problems shown to be FNP-complete under ASP reducibility.  Also, there are several papers on this subject by Takayuki and others (including one paper where I am a coauthor :) ), and Takayuki wrote a PhD thesis on this topic.  One of the later improvements is a formulation based on promise problems, which becomes essential particularly when we deal with PSPACE-completeness and EXP-completeness of ASPs.  Unfortunately, none of the papers seems to be freely available (I feel stupid, but even I cannot access my own paper behind the paywall).  You may want to contact him.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-06T05:23:36.220Z
+1 for a great answer, and for "even I cannot access my own paper behind the paywall", hehe
Daniel Apon
CC BY-SA 2.5
2010-12-05T23:42:57.657Z
2010-12-05T23:54:38.883Z
2010-12-05T23:54:38.883Z
Tsuyoshi Ito
<p>Laurent Juban in <a href="http://www.springerlink.com/content/kayaxnxakp4r56ep/" rel="nofollow noreferrer">Dichotomy Theorem for
the Generalized Unique Satisability Problem</a> proved a dichotomy theorem for <strong>Another SAT</strong> defined as:</p>
<p>Input: a propositional formula <span class="math-container">$\phi$</span> and a satisfying assignment (model) <span class="math-container">$m$</span> of <span class="math-container">$\phi$</span></p>
<p>Question: Is there another satisfying assignment of <span class="math-container">$\phi$</span> different from <span class="math-container">$m$</span>?</p>
<p>Here an excerpt from the paper with the dichotomy theorem:</p>
<blockquote>
<p>Theorem 1 (Dichotomy Theorem). Let <span class="math-container">$S$</span> be a finite set of logical relations.
If <span class="math-container">$S$</span> satisfies one of the conditions (1) to (6) below, then ANOTHER SAT(S) and
UNIQUE SAT(S) are polynomial-time solvable. Otherwise, ANOTHER SAT(S) is
<span class="math-container">$NP$</span>-complete and UNIQUE SAT(S) is <span class="math-container">$coNP$</span>-hard.</p>
</blockquote>
<blockquote>
<ol>
<li>Every satisfiable relation in <span class="math-container">$S$</span> is 0-valid and 1-valid.</li>
</ol>
</blockquote>
<blockquote>
<ol start="2">
<li>Every relation in <span class="math-container">$S$</span> is complementive.</li>
</ol>
</blockquote>
<blockquote>
<ol start="3">
<li>Every relation in <span class="math-container">$S$</span> is Horn.</li>
</ol>
</blockquote>
<blockquote>
<ol start="4">
<li>Every relation in <span class="math-container">$S$</span> is anti-Horn.</li>
</ol>
</blockquote>
<blockquote>
<ol start="5">
<li>Every relation in <span class="math-container">$S$</span> is affine.</li>
</ol>
</blockquote>
<blockquote>
<ol start="6">
<li>Every relation in <span class="math-container">$S$</span> is 2SAT.</li>
</ol>
</blockquote>

CC BY-SA 3.0
2012-11-02T17:00:05.877Z
Yet another variant of Shaefer’s theorem which is false as stated. Let $S=\{\bot,x\lor y\lor\neg z,x\lor\neg y\lor\neg z\}$. Then $S$ violates all six conditions, but both problems are poly-time for $S$: if an $S$-formula contains $\bot$, it is not satisfiable at all. Otherwise, it is in fact an $S'$-formula, where $S'=S\setminus\{\bot\}$ obeys condition 1, hence it has at least two explicitly given satisfying assignments.
Emil Jeřábek
CC BY-SA 3.0
2012-11-02T17:08:23.690Z
That is, in order for the theorem to hold, condition 1 must be corrected to “every *satisfiable* relation in $S$ is 0-valid and 1-valid”.
Emil Jeřábek
CC BY-SA 4.0
2010-12-06T05:11:23.117Z
2021-04-18T14:59:29.820Z
2021-04-18T14:59:29.820Z
Mohammad Al-Turkistany
<p>Given a Hamilton circuit in a graph find another hamilton circuit. This is FNP-complete. Interestingly, there are problems in which the "another solution" is guaranteed to exist by a parity argument. For example : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit. Note that finding a hamiltonian circuit in 3-regular graph is NP-complete. Finding the second one, given that the graph is hamiltonian, is in PPA.</p>

<p>See my <a href="http://kintali.wordpress.com/2009/07/25/finding-a-second-hamilton-circuit/">blog post</a> for more details.</p>

CC BY-SA 2.5
2010-12-06T04:23:06.667Z
NAE-SAT as well. it always has an even number of solutions.
Suresh Venkat
CC BY-SA 2.5
2010-12-06T05:37:23.930Z
According to the above dichotomy, Another NAE-SAT is polynomially solvable (as stated in the paper).
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-06T07:08:26.057Z
Sure. but it's a lot easier for NAE-SAT: take the given assignment and flip it. linear time ! :)
Suresh Venkat
CC BY-SA 2.5
2010-12-06T00:18:59.547Z
2010-12-06T00:18:59.547Z
Shiva Kintali
<p>Here is another example from this paper <a href="https://doi.org/10.1007/BFb0073124" rel="nofollow noreferrer" title="Colbourn, C.J., Colbourn, M.J., Stinson, D.R. (1984). In: Koh, K.M., Yap, H.P. (eds) Graph Theory Singapore 1983. Lecture Notes in Mathematics, vol 1073. Springer, Berlin, Heidelberg.">THE COMPUTATIONAL COMPLEXITY OF RECOGNIZING CRITICAL SETS</a>:</p>
<p>Unique edge-partitioning into triangles is <span class="math-container">$NP$</span>-complete</p>
<p><strong>Input</strong>: Tripartite graph <span class="math-container">$G$</span> and an edge partition into triangles</p>
<p><strong>Question</strong>: Is there another edge-partition different from the given one?</p>
<p>The paper also proves that <span class="math-container">$NP$</span>-completeness of this problem</p>
<p><strong>Input</strong>: Partial Latin square <span class="math-container">$P$</span> with a given a Latin square completing <span class="math-container">$P$</span></p>
<p><strong>Question</strong>: Is there another completion to a Latin square?</p>

CC BY-SA 4.0
2010-12-06T01:21:42.097Z
2023-03-03T09:19:32.183Z
2023-03-03T09:19:32.183Z
Mohammad Al-Turkistany
<p>I'm looking to figure out whether there are any general results about or examples concerning the NP-completeness of the problem of finding a second solution to an NP-complete problem.  More precisely, I'm interested in any problems of the following form:</p>

<p>Given a solution $S$ to an instance $I$ of an NP-complete problem, is there a solution $S' \neq S$ to $I$?</p>

<p>Any examples of problems of this sort, both NP-complete and not, or general work, or even a what this sort of problem is called (so I can properly do my own searching) would be appreciated.</p>

<p><a href="https://cstheory.stackexchange.com/questions/1639/verifying-unique-solutions-of-sat">Another question</a> addresses this issue specifically as pertaining to SAT.</p>

<p>I hope I'm not asking something really basic; there don't seem to be any examples in Garey and Johnson of this kind of thing.</p>

<p>Thanks<br/>
Mark C.</p>

CC BY-SA 2.5
2010-12-05T23:31:27.027Z
Mark, if http://cstheory.stackexchange.com/questions/1639/verifying-unique-solutions-of-sat answers your question, do let me know, and we can mark this as a duplicate. I'm asking because your question seems quite open ended, and maybe the answers there might help
Suresh Venkat
CC BY-SA 2.5
2010-12-05T23:36:59.533Z
Ah, yes, it does seem to answer it.  Clearly, "Another Solution Problem" is what I was looking for.   Thank you!
Mark C.
CC BY-SA 2.5
2010-12-05T23:50:19.680Z
Tsuyoshi's answer seems quite distinct from the other ones, so I'm not sure it makes sense to close this question. Maybe Mark, you could add a note to the question forwarding readers to the other question (which is specific to SAT) ?
Suresh Venkat
<cc.complexity-theory><reference-request><np-hardness><unique-solution>
Complexity of finding a second solution given a correct solution to an NP-complete problem
Mark C.
# Complexity of finding a second solution given a correct solution to an NP-complete problem

(Asked by: username_0 on 2010-12-05)

I'm looking to figure out whether there are any general results about or examples concerning the NP-completeness of the problem of finding a second solution to an NP-complete problem. More precisely, I'm interested in any problems of the following form:

Given a solution $S$ to an instance $I$ of an NP-complete problem, is there a solution $S' \neq S$ to $I$?

Any examples of problems of this sort, both NP-complete and not, or general work, or even a what this sort of problem is called (so I can properly do my own searching) would be appreciated.

[Another question](https://cstheory.stackexchange.com/questions/1639/verifying-unique-solutions-of-sat) addresses this issue specifically as pertaining to SAT.

I hope I'm not asking something really basic; there don't seem to be any examples in Garey and Johnson of this kind of thing.

Thanks  
username_0

**Tags:** cc.complexity-theory, reference-request, np-hardness, unique-solution

> **Comments:**
> **username_1**: Mark, if http://cstheory.stackexchange.com/questions/1639/verifying-unique-solutions-of-sat answers your question, do let me know, and we can mark this as a duplicate. I'm asking because your question seems quite open ended, and maybe the answers there might help  
> **username_0**: Ah, yes, it does seem to answer it.  Clearly, "Another Solution Problem" is what I was looking for.   Thank you!  
> **username_1**: Tsuyoshi's answer seems quite distinct from the other ones, so I'm not sure it makes sense to close this question. Maybe Mark, you could add a note to the question forwarding readers to the other question (which is specific to SAT) ?  

---

## 4 answers

### Answer by username_2 on 2010-12-05. Score: 17

The question seems to be solved while I was writing this answer, but let me post my answer anyway.

Yato and Seta [YS03] (both are my colleagues when I was a student) propose a general framework to prove the NP-completeness of this kind of problems, where they are called Another Solution Problems or ASPs, and prove the NP-completeness of the ASPs of many puzzles. They consider a restricted notion of reductions between relation problems called ASP reductions, and show that the NP-hardness of ASPs is preserved under ASP reductions and show that many known reductions can be in fact viewed as or modified to ASP reductions between natural relation problems.

[YS03] Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. *IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences*, E86-A(5):1052–1060, May 2003.

> **Comments:**
> **username_3**: I know someone who is considering this as a possible direction for a PhD thesis, and we talked about it briefly, though I know nothing about the area.  It doesn't seem as though there's been much followup since the paper you cite, though perhaps my search skills are weak.  Are you aware of any significant papers since 2003?  
> **username_2**: @Aaron: There are other problems shown to be FNP-complete under ASP reducibility.  Also, there are several papers on this subject by Takayuki and others (including one paper where I am a coauthor :) ), and Takayuki wrote a PhD thesis on this topic.  One of the later improvements is a formulation based on promise problems, which becomes essential particularly when we deal with PSPACE-completeness and EXP-completeness of ASPs.  Unfortunately, none of the papers seems to be freely available (I feel stupid, but even I cannot access my own paper behind the paywall).  You may want to contact him.  
> **username_4**: +1 for a great answer, and for "even I cannot access my own paper behind the paywall", hehe  

---

### Answer by username_5 on 2010-12-06. Score: 9

Laurent Juban in [Dichotomy Theorem for
the Generalized Unique Satisability Problem](http://www.springerlink.com/content/kayaxnxakp4r56ep/) proved a dichotomy theorem for **Another SAT** defined as:

Input: a propositional formula $\phi$ and a satisfying assignment (model) $m$ of $\phi$

Question: Is there another satisfying assignment of $\phi$ different from $m$?

Here an excerpt from the paper with the dichotomy theorem:

> Theorem 1 (Dichotomy Theorem). Let $S$ be a finite set of logical relations.
> If $S$ satisfies one of the conditions (1) to (6) below, then ANOTHER SAT(S) and
> UNIQUE SAT(S) are polynomial-time solvable. Otherwise, ANOTHER SAT(S) is
> $NP$-complete and UNIQUE SAT(S) is $coNP$-hard.

> 1. Every satisfiable relation in $S$ is 0-valid and 1-valid.

> 2. Every relation in $S$ is complementive.

> 3. Every relation in $S$ is Horn.

> 4. Every relation in $S$ is anti-Horn.

> 5. Every relation in $S$ is affine.

> 6. Every relation in $S$ is 2SAT.

> **Comments:**
> **username_6**: Yet another variant of Shaefer’s theorem which is false as stated. Let $S=\{\bot,x\lor y\lor\neg z,x\lor\neg y\lor\neg z\}$. Then $S$ violates all six conditions, but both problems are poly-time for $S$: if an $S$-formula contains $\bot$, it is not satisfiable at all. Otherwise, it is in fact an $S'$-formula, where $S'=S\setminus\{\bot\}$ obeys condition 1, hence it has at least two explicitly given satisfying assignments.  
> **username_6**: That is, in order for the theorem to hold, condition 1 must be corrected to “every *satisfiable* relation in $S$ is 0-valid and 1-valid”.  

---

### Answer by username_7 on 2010-12-06. Score: 8

Given a Hamilton circuit in a graph find another hamilton circuit. This is FNP-complete. Interestingly, there are problems in which the "another solution" is guaranteed to exist by a parity argument. For example : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit. Note that finding a hamiltonian circuit in 3-regular graph is NP-complete. Finding the second one, given that the graph is hamiltonian, is in PPA.

See my [blog post](http://kintali.wordpress.com/2009/07/25/finding-a-second-hamilton-circuit/) for more details.

> **Comments:**
> **username_1**: NAE-SAT as well. it always has an even number of solutions.  
> **username_5**: According to the above dichotomy, Another NAE-SAT is polynomially solvable (as stated in the paper).  
> **username_1**: Sure. but it's a lot easier for NAE-SAT: take the given assignment and flip it. linear time ! :)  

---

### Answer by username_5 on 2010-12-06. Score: 1

Here is another example from this paper [THE COMPUTATIONAL COMPLEXITY OF RECOGNIZING CRITICAL SETS](https://doi.org/10.1007/BFb0073124 "Colbourn, C.J., Colbourn, M.J., Stinson, D.R. (1984). In: Koh, K.M., Yap, H.P. (eds) Graph Theory Singapore 1983. Lecture Notes in Mathematics, vol 1073. Springer, Berlin, Heidelberg."):

Unique edge-partitioning into triangles is $NP$-complete

**Input**: Tripartite graph $G$ and an edge partition into triangles

**Question**: Is there another edge-partition different from the given one?

The paper also proves that $NP$-completeness of this problem

**Input**: Partial Latin square $P$ with a given a Latin square completing $P$

**Question**: Is there another completion to a Latin square?


---

