In this question, we appear to have identified a natural problem that is NP-complete under randomized reductions, but possibly not under deterministic reductions (although this depends on which unproven assumptions in number theory are true). Are there any other such problems known? Are there any natural problems that are NP-complete under P/poly reductions, but not known to be under P reductions?
$\begingroup$
$\endgroup$
12
-
7$\begingroup$ Unique SAT is $NP$-hard under randomized reduction. $\endgroup$– Mohammad Al-TurkistanyCommented Feb 8, 2011 at 16:45
-
7$\begingroup$ I don't see why Unique SAT shouldn't count as an answer (even though that wasn't quite what I was looking for). I think it counts as a natural problem. $\endgroup$– Peter ShorCommented Feb 8, 2011 at 17:06
-
6$\begingroup$ I just wanted to add that the shortest vector problem for LLL under $L_2$ norm for randomized reductions (paper by Ajtai here) is NP-Hard. As far as I know it is not known to be NP-Hard under non-random reductions, so it doesn't meet your criteria, but I thought it should be mentioned anyway. $\endgroup$– user834Commented Feb 8, 2011 at 17:30
-
4$\begingroup$ @Joshua: In some NP-complete problems related to puzzles (such as Sudoku), uniqueness of a solution is a natural assumption. I guess that this makes the SAT with at most one solution (I prefer to call it Unambiguous SAT) more natural than it might first seem. $\endgroup$– Tsuyoshi ItoCommented Feb 8, 2011 at 20:55
-
10$\begingroup$ Why is everybody writing answers in comments? :P $\endgroup$– Hsien-Chih Chang 張顯之Commented Feb 9, 2011 at 1:44
|
Show 7 more comments
3 Answers
$\begingroup$
$\endgroup$
Under randomized reduction with probability $\frac{1}{2}$ (known also as $\gamma$-reducibility, on the discussion of randomized reductions see "On Unique Satisfiability and Randomized Reductions") problems
- Linear divisibility
- Binary quadratic diophantine equations
are NP-complete, but the same is not known for deterministic reductions (as far as I know, for slightly out-dated discussion of this situation see here). $\gamma$-reducibility was introduced in the paper "Reducibility, randomness, and intractibility" by Leonard Adleman and Kenneth Manders (proofs for the problems above were proposed also there).
There are other such examples in "A Catalog of Complexity Classes", but I haven't checked what is known about their NP-completeness under deterministic reductions.
answered Feb 9, 2011 at 10:07
$\begingroup$
$\endgroup$
As suggested by Peter, I converted my comment into an answer.
Valiant-Vazirani Theorem states that if Unique SAT $\in P$ then $NP=RP$. To prove their theorem they showed that the promise problem Unique SAT is $NP$-hard under randomized reductions.
[1] Valiant, Leslie; Vazirani, Vijay. "NP is as easy as detecting unique solutions", Theoretical Computer Science, 47: 85–93
answered Feb 9, 2011 at 7:08
$\begingroup$
$\endgroup$
As suggested by Peter, I converted my comment to an answer:
M. Ajtai's paper "The Shortest Vector Problem in $L_2$ is $NP$-hard for Randomized Reductions." discusses complexity results of finding shortest vectors for lattice reduction using randomized reduction steps.
