<p>Shortest 2-Vertex disjoint path problem in undirected graphs <a href="http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf">recently solved</a> (ICALP14) by A. Bjorklund and T. Husfeldt. But the deterministic solution is for the case of existence of a  unique solution. In the case that there are more than one solution, they showed that the problem belongs to <strong>RP</strong>. As authors of the paper mentioned, it is not known if the problem is in <strong>P</strong> in general scenario.</p>

CC BY-SA 3.0
2014-05-01T20:14:35.240Z
Thank you, it is very interesting. The general case, where the solution is not unique,  is also a nice example of a natural (or even practical) graph problem, which is now proved to be in RP, but not known to be in P.
Andras Farago
CC BY-SA 3.0
2014-05-01T19:33:19.563Z
2014-05-12T16:56:01.230Z
2014-05-12T16:56:01.230Z
Saeed
<p>Outside of complexity theory and the analysis of algorithms, the assumption that there can be only one solution forms the basis for some of the standard rules used to deduce the solution in Sudoku puzzles. These rules generally involve looking for ways in which parts of the puzzle might be able to have two or more solutions that don't interact with the rest of the puzzle. That can't happen in the actual solution, so if a pattern that threatens to cause this is found, then it must be broken, allowing the solver to deduce constraints on what the actual solution can look like. See <a href="http://www.brainbashers.com/sudokuuniquerectangles.asp">http://www.brainbashers.com/sudokuuniquerectangles.asp</a> for some examples of deduction rules based on uniqueness.</p>

CC BY-SA 3.0
2014-07-23T16:30:47.437Z
2014-07-23T16:30:47.437Z
David Eppstein
<p>Mentioning another result by Björklund, if you are guaranteed that there is at most one Hamiltonian cycle in a graph, you can decide if a graph $G$ is Hamiltonian faster than you can in general.</p>

<p>The uniqeness assumption means that the parity of the number of Ham. paths is the same as deciding if the graph is Hamiltonian.</p>

<p><a href="http://arxiv.org/pdf/1301.7250.pdf">Björklund's method</a> deterministically computes the parity of the number of Hamiltonian cycles in $O(1.619^n)$ while the <a href="http://arxiv.org/abs/1008.0541">best known randomized algorithm</a> for Undirected Hamiltonicity runs in $O^*(1.657^n)$ , and the best deterministic algorithm for Directed Hamiltonicity (to the best of my knowledge) is still the 50 years old $O(n^22^n)$ dynamic programming algorithm by Bellman, Held and Karp.</p>

CC BY-SA 3.0
2014-07-22T14:20:08.733Z
2014-07-23T16:00:17.337Z
2014-07-23T16:00:17.337Z
R B
<p>3-SAT may be one such problem.  Currently the best upper bound for Unique 3-SAT is exponentially faster than for general 3-SAT.  (The speedup is exponential, although the reduction in the exponent is tiny.)  The record-holder for the unique case is <a href="http://arxiv.org/pdf/1311.2513v2.pdf">this paper</a> by Timon Hertli.</p>

<p>Hertli's algorithm builds upon the important <a href="http://cseweb.ucsd.edu/users/paturi/myPapers/pubs/PaturiPudlakSaksZane_2005_jacm.pdf">PPSZ algorithm</a> of Paturi, Pudlák, Saks, and Zane for $k$-SAT, which I believe is still the fastest for $k \geq 5$ (see also <a href="http://cseweb.ucsd.edu/users/paturi/myPapers/pubs/PaturiPudlakSaksZane_2008_encyc.pdf">this</a> encyclopedia article).  The original analysis showed better bounds for Unique $k$-SAT than for general $k$-SAT when $k = 3, 4$; subsequently, however, Hertli showed in a different <a href="http://arxiv.org/pdf/1103.2165v2.pdf">paper</a> that you could get the same bounds for (a slightly tweaked) PPSZ algorithm, without assuming uniqueness.  So, maybe uniqueness helps, and it can definitely simplify the analysis of some algorithms, but our understanding of the role of uniqueness for $k$-SAT is still growing.</p>

<p>There is evidence that Unique $k$-SAT is not <em>too much</em> easier than general $k$-SAT. The Strong Exponential Time Hypothesis (SETH) asserts there is no $\delta &lt; 1$ such that $n$-variable $k$-SAT is solvable in $O^*(2^{\delta n})$ time for each constant $k \geq 3$. It was shown in a <a href="http://cseweb.ucsd.edu/users/paturi/myPapers/pubs/CalabroImpagliazzoKabanetsPaturi_2008_jcss.pdf">paper</a> of Calabro, Impagliazzo, Kabanets, and Paturi that, if SETH holds, then the same statement is true for Unique $k$-SAT.  Also, if general $k$-SAT  requires exponential time, i.e. there is some $k \geq 3, \epsilon &gt; 0$ such that general $k$-SAT cannot be solved in time $O^*(2^{\epsilon n})$, then the same must be true for Unique 3-SAT.  See the paper for the most general statement.  </p>

<p>(Note: the $O^*$ notation suppresses polynomial factors in the input length.)</p>

CC BY-SA 3.0
2014-04-13T20:53:54.800Z
Hi Ricky, I don't see a problem with what's written.  The last assertion about Unique 3-SAT is found in the paper's abstract.
Andy Drucker
CC BY-SA 3.0
2014-04-13T13:17:49.740Z
2014-04-13T13:37:22.223Z
2014-04-13T13:37:22.223Z
Andy Drucker
<p>The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. That is, the solution, if any, is <em>unique</em> in this sense. 
It is thought highly unlikely that all $\mathsf{UP}$-problems are in $\mathsf{P}$, because by the <a href="http://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem">Valiant-Vazirani Theorem</a> this would imply the collapse $\mathsf{NP}=\mathsf{RP}$.</p>

<p>On the other hand, no $\mathsf{UP}$-problem is known to be $\mathsf{NP}$-complete, which suggests that the unique solution requirement still somehow makes them easier.</p>

<blockquote>
  <p>I am looking for examples, where  the uniqueness assumption leads to a faster algorithm. </p>
</blockquote>

<p>For example, looking at graph problems, can a maximum clique in a graph be found faster (though possibly still in exponential time), if we know that the graph has a <em>unique</em> maximum clique? How about unique $k$-colorability, unique Hamiltonian path, unique minimum dominating set etc.? </p>

<p>In general, we can define a      unique-solution version of <em>any</em> $\mathsf{NP}$-complete problem, scaling them down to $\mathsf{UP}$. Is it known for any of them that adding the uniqueness assumption leads to a faster algorithm? (Allowing that it still remains exponential.)</p>

CC BY-SA 3.0
2014-04-13T02:49:04.587Z
Your first sentence gives the correct definition of UP, but the rest of your references to UP should really be to PromiseUP instead (including Valiant-Vazirani). Either way this is a very interesting question. Two examples: 1) Factoring is in UP, and has an algorithm faster than those known for NP-complete problems (but Factoring is also in coNP and even coUP, so it's not so clear that *uniqueness* is underlying the fast algorithm here.) 2) Sodoku, as traditionally defined, is in PromiseUP, yet I don't know of any approaches to Sudoku-solving that take advantage of the promised uniqueness.
Joshua Grochow
CC BY-SA 3.0
2014-04-13T04:06:24.037Z
The parity of the number of Hamiltonian paths can be found in time $1.618^n$ (http://arxiv.org/pdf/1301.7250.pdf), while the best known algorithm for the decision problem takes almost $2^n$ time.
Alex Golovnev
CC BY-SA 3.0
2014-04-13T13:45:28.207Z
Here's an example from quantum computing: Consider the search problem on n items. If you know there is exactly 1 marked item, you can find it with an exact quantum algorithm with $\Theta(\sqrt{n})$ queries. If you don't know the number of marked items, any exact quantum algorithm needs $n$ queries.
Robin Kothari
<cc.complexity-theory><ds.algorithms><graph-algorithms><complexity-classes><unique-solution>
Examples where the uniqueness of the solution makes it easier to find
Andras Farago
# Examples where the uniqueness of the solution makes it easier to find

(Asked by: username_0 on 2014-04-12)

The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. That is, the solution, if any, is *unique* in this sense.
It is thought highly unlikely that all $\mathsf{UP}$-problems are in $\mathsf{P}$, because by the [Valiant-Vazirani Theorem](http://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem) this would imply the collapse $\mathsf{NP}=\mathsf{RP}$.

On the other hand, no $\mathsf{UP}$-problem is known to be $\mathsf{NP}$-complete, which suggests that the unique solution requirement still somehow makes them easier.

> I am looking for examples, where the uniqueness assumption leads to a faster algorithm.

For example, looking at graph problems, can a maximum clique in a graph be found faster (though possibly still in exponential time), if we know that the graph has a *unique* maximum clique? How about unique $k$-colorability, unique Hamiltonian path, unique minimum dominating set etc.?

In general, we can define a unique-solution version of *any* $\mathsf{NP}$-complete problem, scaling them down to $\mathsf{UP}$. Is it known for any of them that adding the uniqueness assumption leads to a faster algorithm? (Allowing that it still remains exponential.)

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, complexity-classes, unique-solution
> **Comments:**
> **username_1**: Your first sentence gives the correct definition of UP, but the rest of your references to UP should really be to PromiseUP instead (including Valiant-Vazirani). Either way this is a very interesting question. Two examples: 1) Factoring is in UP, and has an algorithm faster than those known for NP-complete problems (but Factoring is also in coNP and even coUP, so it's not so clear that *uniqueness* is underlying the fast algorithm here.) 2) Sodoku, as traditionally defined, is in PromiseUP, yet I don't know of any approaches to Sudoku-solving that take advantage of the promised uniqueness.  
> **username_2**: The parity of the number of Hamiltonian paths can be found in time $1.618^n$ (http://arxiv.org/pdf/1301.7250.pdf), while the best known algorithm for the decision problem takes almost $2^n$ time.  
> **username_3**: Here's an example from quantum computing: Consider the search problem on n items. If you know there is exactly 1 marked item, you can find it with an exact quantum algorithm with $\Theta(\sqrt{n})$ queries. If you don't know the number of marked items, any exact quantum algorithm needs $n$ queries.  

---

## 4 answers

### Answer by username_7 on 2014-04-13. Score: 23 | Accepted answer

3-SAT may be one such problem. Currently the best upper bound for Unique 3-SAT is exponentially faster than for general 3-SAT. (The speedup is exponential, although the reduction in the exponent is tiny.) The record-holder for the unique case is [this paper](http://arxiv.org/pdf/1311.2513v2.pdf) by Timon Hertli.

Hertli's algorithm builds upon the important [PPSZ algorithm](http://cseweb.ucsd.edu/users/paturi/myPapers/pubs/PaturiPudlakSaksZane_2005_jacm.pdf) of Paturi, Pudlák, Saks, and Zane for $k$-SAT, which I believe is still the fastest for $k \geq 5$ (see also [this](http://cseweb.ucsd.edu/users/paturi/myPapers/pubs/PaturiPudlakSaksZane_2008_encyc.pdf) encyclopedia article). The original analysis showed better bounds for Unique $k$-SAT than for general $k$-SAT when $k = 3, 4$; subsequently, however, Hertli showed in a different [paper](http://arxiv.org/pdf/1103.2165v2.pdf) that you could get the same bounds for (a slightly tweaked) PPSZ algorithm, without assuming uniqueness. So, maybe uniqueness helps, and it can definitely simplify the analysis of some algorithms, but our understanding of the role of uniqueness for $k$-SAT is still growing.

There is evidence that Unique $k$-SAT is not *too much* easier than general $k$-SAT. The Strong Exponential Time Hypothesis (SETH) asserts there is no $\delta < 1$ such that $n$-variable $k$-SAT is solvable in $O^\*(2^{\delta n})$ time for each constant $k \geq 3$. It was shown in a [paper](http://cseweb.ucsd.edu/users/paturi/myPapers/pubs/CalabroImpagliazzoKabanetsPaturi_2008_jcss.pdf) of Calabro, Impagliazzo, Kabanets, and Paturi that, if SETH holds, then the same statement is true for Unique $k$-SAT. Also, if general $k$-SAT requires exponential time, i.e. there is some $k \geq 3, \epsilon > 0$ such that general $k$-SAT cannot be solved in time $O^\*(2^{\epsilon n})$, then the same must be true for Unique 3-SAT. See the paper for the most general statement.

(Note: the $O^\*$ notation suppresses polynomial factors in the input length.)

> **Comments:**
> **username_7**: Hi Ricky, I don't see a problem with what's written.  The last assertion about Unique 3-SAT is found in the paper's abstract.  

---

### Answer by username_4 on 2014-05-01. Score: 18

Shortest 2-Vertex disjoint path problem in undirected graphs [recently solved](http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf) (ICALP14) by A. Bjorklund and T. Husfeldt. But the deterministic solution is for the case of existence of a unique solution. In the case that there are more than one solution, they showed that the problem belongs to **RP**. As authors of the paper mentioned, it is not known if the problem is in **P** in general scenario.

> **Comments:**
> **username_0**: Thank you, it is very interesting. The general case, where the solution is not unique,  is also a nice example of a natural (or even practical) graph problem, which is now proved to be in RP, but not known to be in P.  

---

### Answer by username_5 on 2014-07-23. Score: 11

Outside of complexity theory and the analysis of algorithms, the assumption that there can be only one solution forms the basis for some of the standard rules used to deduce the solution in Sudoku puzzles. These rules generally involve looking for ways in which parts of the puzzle might be able to have two or more solutions that don't interact with the rest of the puzzle. That can't happen in the actual solution, so if a pattern that threatens to cause this is found, then it must be broken, allowing the solver to deduce constraints on what the actual solution can look like. See <http://www.brainbashers.com/sudokuuniquerectangles.asp> for some examples of deduction rules based on uniqueness.


---

### Answer by username_6 on 2014-07-22. Score: 10

Mentioning another result by Björklund, if you are guaranteed that there is at most one Hamiltonian cycle in a graph, you can decide if a graph $G$ is Hamiltonian faster than you can in general.

The uniqeness assumption means that the parity of the number of Ham. paths is the same as deciding if the graph is Hamiltonian.

[Björklund's method](http://arxiv.org/pdf/1301.7250.pdf) deterministically computes the parity of the number of Hamiltonian cycles in $O(1.619^n)$ while the [best known randomized algorithm](http://arxiv.org/abs/1008.0541) for Undirected Hamiltonicity runs in $O^\*(1.657^n)$ , and the best deterministic algorithm for Directed Hamiltonicity (to the best of my knowledge) is still the 50 years old $O(n^22^n)$ dynamic programming algorithm by Bellman, Held and Karp.


---

