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?

  • 7
    $\begingroup$ Unique SAT is $NP$-hard under randomized reduction. $\endgroup$ 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$ 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$
    – user834
    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$ Feb 8, 2011 at 20:55
  • 10
    $\begingroup$ Why is everybody writing answers in comments? :P $\endgroup$ Feb 9, 2011 at 1:44

3 Answers 3


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

  1. Linear divisibility
  2. 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.


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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.