20

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?

Community
  • 1
Peter Shor
  • 24,763
  • 4
  • 93
  • 133
  • 7
    Unique SAT is $NP$-hard under randomized reduction. – Mohammad Al-Turkistany Feb 08 '11 at 16:45
  • @turkistany: I'm not sure how natural UniqueSAT counts as. Note that the same argument (Valiant-Vazirani) applies to any problem that has a parsimonious reduction from SAT. That is, given such a problem X, UniqueX is NP-hard under randomized reductions but not known to be so under deterministic reductions. In contrast, in the case of factoring, the uniqueness is naturally part of the problem, rather than being an additional requirement we tacked onto it. – Joshua Grochow Feb 08 '11 at 16:57
  • (And by "uniqueness" in the case of factoring I didn't mean to imply that there is always a unique $m \in [L, U]$ such that $m | N$, but more of a "moral" uniqueness in the sense that the factorization of $N$ is unique.) – Joshua Grochow Feb 08 '11 at 17:04
  • 7
    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. – Peter Shor Feb 08 '11 at 17:06
  • 6
    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. – user834 Feb 08 '11 at 17:30
  • 1
    I clearly should have said "not known to be" instead of "not", because otherwise we get into computational complexity issues, and there won't be any answers to this question. I'm editing my question. You should make your comment into an answer. – Peter Shor Feb 08 '11 at 17:54
  • 2
    Under randomized reduction with probability $\frac{1}{2}$ problem Linear divisibility (http://books.google.com/books?id=JogZAQAAIAAJ&q=%22linear+divisibility%22&dq=%22linear+divisibility%22&hl=en&ei=_EwxTe2rMsaSOsru9LQC&sa=X&oi=book_result&ct=result&resnum=23&ved=0CIUBEOgBMBY) is NP-complete, but the same is not known for deterministic reductions (as far as I know). – Oleksandr Bondarenko Feb 08 '11 at 18:53
  • 4
    @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. – Tsuyoshi Ito Feb 08 '11 at 20:55
  • 10
    Why is everybody writing answers in comments? :P – Hsien-Chih Chang 張顯之 Feb 09 '11 at 01:44
  • 1
    @Tsuyoshi: Actually, the uniqueness assumption in Sudoku is just tacked onto the end. It just so happens to be part of the puzzle definition: "a solution has each of the numbers 1-n in each row, each column, and each square. Oh, and by the way, all the puzzles we give you have a unique solution." That being said, Unambiguous X is not so unnatural, and whether or not it counts as an answer to this question is really about the threshold of naturality Peter Shor was looking for. Since Unambiguous SAT fits the bill, I assume that also means Unambiguous X fits whenever X is fairly natural. – Joshua Grochow Feb 09 '11 at 04:08
  • 2
    @Joshua: That view on the uniqueness assumption in Sudoku is different from mine. I consider the uniqueness assumption as a primary part of the definition of this kind of puzzles, and in some sense it is more important than the rules of Sudoku. But I understand that this is just a personal view. – Tsuyoshi Ito Feb 09 '11 at 04:35
  • @user834: Your comment really should be an answer. Do you want to post it as one? – Peter Shor Feb 10 '11 at 19:37

3 Answers3

12

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

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
10

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.

Oleksandr Bondarenko
  • 4,215
  • 1
  • 25
  • 46
9

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.

user834
  • 2,806
  • 21
  • 27