# Tag Info

23

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 by Timon Hertli. Hertli's algorithm builds upon the important PPSZ algorithm of Paturi, Pudlák, ...

17

Shortest 2-Vertex disjoint path problem in undirected graphs recently solved (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 ...

12

No NP-complete problem is known to admit a polynomial-time algorithm under uniqueness promise. Valiant and Vazirani theorem applies to any known natural NP-complete problem. For all known NP-complete problems, there is a parsimonious reduction from 3SAT. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are ...

11

OptP-complete. Krentel showed that MAX-SAT, finding the lexicographically maximum satisfying assignment, is OptP-complete and the reduction above reduces Max-SAT to ILP. ILP sits in OptP pretty much by definition. Note that you need n calls to an NP-oracle to solve ILP via binary search, O(log n) isn't sufficient. There really isn't much of a connection ...

10

No, Consider the problem "Find a subset of a set of integers S which sums to 0". This problem is trivial, as one can return the empty set. However, finding a second solution after returning the empty set is the well-known subset sum problem, which is known to be NP-complete.

10

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

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

10

Yes, there is a natural NP-complete problem for which uniqueness makes it easy: $k$-edge coloring for $k\ge 4$. Here, to make uniqueness possible, a coloring is defined as a partition of the edges into nonempty matchings, irrespective of the ordering or labeling of the matchings in the partition. All graphs have edge-colorings with one more color than degree ...

5

Yes, there is such a problem. While the problem is arguably not "natural", it is certainly NP-complete. The problem is: for a degree 3 graph $G$, is $G$ either planar or Hamiltonian (i.e., has a Hamiltonian cycle)? If $G$ has a Hamiltonian cycle, then it has at least two Hamiltonian cycles (this is a theorem for degree 3 graphs; see the comments to ...

5

Even, Selman, and Yacobi conjectured that there does not exist a disjoint $NP$-pair $(A, B)$ such that all separators of $(A, B)$ are $\le_T^p$-hard for $NP$. This conjecture implies that $UP \ne NP$. S. Even, A. Selman, and J. Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61:159–173, ...

4

It is known that $\mathsf{UP= NP}$ implies $\mathsf{SpanP = \#P}$ since Kobler, Schoning, and Toran proved that $\mathsf{UP= NP}$ if and only if $\mathsf{SpanP = \#P}$. It is easy to see that $\mathsf {\#P}$ is contained in $\mathsf {SpanP}$. A function $f : Σ^* →\mathbb N$ is in $\mathsf{SpanP}$ if there is an $\mathsf {NP}$ Turing machine transducer $M$ ...

4

As far as I can tell, UniqueSAT is exponentially dense, in the sense that it contains $2^{\Omega(n)}$ instances of size $n$. (This is a stronger requirement than $2^{n^\varepsilon}$ for infinitely many $n$.) The following argument works even for the revised definition of "dense" introduced in version 5 of the question, where all instances of size up to $n$ ...

4

Let an ASP-complete problem Q be given. There is an ASP-reduction from 3SAT to Q and all ASP-reductions are parsimonious, hence it serves as a parsimonious reduction from #3SAT to #Q. Since #Q is in #P and #3SAT is #P-hard, #Q is #P-complete.

2

It puts NP into P/poly, and therefore collapses PH to its second level. By basically the same as the usual proof that BPP is in P/poly, there is polynomial advice that provides good random bits for the randomized reduction of Valiant-Vazirani. Use that advice to produce the queries to UnambiguousSAT. Apply the reduction from UnambiguousSAT to the sparse ...

2

The solution to both problems, UNIQUE SAT as well as ANOTHER SAT, with a complete classification of complexity, can be found in the paper L. Juban: Dichotomy theorem for the generalized unique satisfiability problem http://link.springer.com/chapter/10.1007%2F3-540-48321-7_27

1

Koiran's paper Hilbert's Nullstellensatz is in the Polynomial Hierarchy provides a public-coin Arthur-Merlin protocol for establishing that a system of $m$ equations on $n$ unknowns has a solution in $\mathbb{C}^n$, contingent on the Generalized Riemann Hypothesis. Here Merlin finds a prime $p$ with $H(p)=0$ for some random hash $H$, along with a solution \$(...

Only top voted, non community-wiki answers of a minimum length are eligible