The 2024 Developer Survey results are live! See the results

# Tag Info

Accepted

### NP-Complete problems that admit an efficient algorithm under the promise of a unique solution

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

### Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

For notational convenience define r.v.s $T_S = \min\{i : |S_i| = 1\}$ (recalling $S_i = S \cap H_1 \cap \cdots \cap H_i$), and $T_H = \min\big\{i : H_1 \cap H_2 \cap \cdots \cap H_i = \{0^n\}\big\}$. ...
• 10.8k

### Does “Second X is NP-complete” imply “X is NP-complete”?

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

### NP-Complete problems that admit an efficient algorithm under the promise of a unique solution

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 ...
• 51.1k

### NP-Complete problems that admit an efficient algorithm under the promise of a unique solution

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., ...
• 24.9k
Accepted

### What's the relationship between ASP-complete and #P-complete?

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 ...
• 249
Accepted

### Unambiguous SAT and sparse languages

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 ...
• 37.8k
1 vote

### Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?

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 \$...
• 1,135

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