20
$\begingroup$

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?

$\endgroup$
  • 7
    $\begingroup$ Unique SAT is $NP$-hard under randomized reduction. $\endgroup$ – Mohammad Al-Turkistany Feb 8 '11 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 Shor Feb 8 '11 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 '11 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 Ito Feb 8 '11 at 20:55
  • 10
    $\begingroup$ Why is everybody writing answers in comments? :P $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 9 '11 at 1:44
10
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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