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


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


3

$\def\mr{\mathrm}$First, standard derandomization assumptions (the existence of a language in $\mr E$ that requires circuit size $2^{\Omega(n)}$) imply $\mr{promise\text-BPP=promise\text-P}$, hence $$\mr{MA=\exists BPP=NP},$$ thus any difference between the two classes is likely just an artifact of our incomplete knowledge. Having said that, there are ...


2

Concerning the question whether Shaefer’s dichotomy theorem (or more generally, the Feder–Vardi conjecture, recently proved by Bulatov and Zhuk) can be generalized to promise problems: the complexity of promise CSPs is currently a hot research topic. It is still very much open if there is such a dichotomy even for Boolean PCSPs. However, partial results are ...


1

Let's define what P$^A$ means in the promise setting: A language L is in P$^A$ if there is a polytime oracle machine $M$ such that for all sets $B$ such that $B$ contains $A_{YES}$ and $B\cap A_{NO}=\emptyset$, $L=L(M^B)$. In other words, the polytime machine can ask queries that are not part of the promise but its output cannot depend on whether those ...


1

Aaronson is working within a particular context, but if you take his statement in an absolute sense, you're right to be skeptical. Translated into “physics language,” the question is this: suppose we had an efficient classical algorithm to estimate the expectation value of any observable in quantum mechanics. This is technically imprecise. PromiseBQP and ...


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