<p>As suggested by Peter, I converted my comment into an answer. </p>

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

<p>[1] Valiant, Leslie; Vazirani, Vijay. "NP is as easy as detecting unique solutions", Theoretical Computer Science, 47: 85–93</p>

CC BY-SA 2.5
2011-02-09T07:08:42.437Z
2011-02-09T07:08:42.437Z
Mohammad Al-Turkistany
<p>As suggested by Peter, I converted my comment to an answer:</p>

<p>M. Ajtai's paper <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.3023&amp;rep=rep1&amp;type=pdf">"The Shortest Vector Problem in $L_2$ is $NP$-hard for Randomized Reductions."</a> discusses complexity results of finding shortest vectors for lattice reduction using randomized reduction steps.</p>

CC BY-SA 2.5
2011-02-24T20:24:46.083Z
2011-02-24T20:24:46.083Z
user834
<p>Under randomized reduction with probability $\frac{1}{2}$ (known also as <a href="http://scholar.google.com/scholar?hl=en&amp;q=%22gamma-reducibility%22&amp;btnG=Search&amp;as_sdt=1,5&amp;as_ylo=&amp;as_vis=0">$\gamma$-reducibility</a>, on the discussion of randomized reductions see "<a href="http://scholar.google.com/scholar?q=%22On%20unique%20satisfiability%20and%20randomized%20reductions%22&amp;um=1&amp;ie=UTF-8&amp;sa=N&amp;hl=en&amp;tab=ws">On Unique Satisfiability and Randomized Reductions</a>") problems</p>

<ol>
<li><a href="http://books.google.com/books?id=JogZAQAAIAAJ&amp;q=%22linear+divisibility%22&amp;dq=%22linear+divisibility%22&amp;hl=en&amp;ei=oVtSTYGlFIy28QPf9YmjCw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=22&amp;ved=0CIcBEOgBMBU">Linear divisibility</a></li>
<li>Binary quadratic diophantine equations</li>
</ol>

<p>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 <a href="http://books.google.com/books?id=-X39_rA3VSQC&amp;pg=PA90&amp;dq=%22linear+divisibility%22&amp;hl=en&amp;ei=oVtSTYGlFIy28QPf9YmjCw&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=11&amp;ved=0CFQQ6AEwCg#v=onepage&amp;q=%22linear%20divisibility%22&amp;f=false">here</a>). $\gamma$-reducibility was introduced in the paper "<a href="http://scholar.google.com/scholar?q=%22reducibility,+randomness,+and+intractibility%22+&amp;hl=en&amp;btnG=Search&amp;as_sdt=1,5">Reducibility, randomness, and intractibility</a>" by Leonard  Adleman and Kenneth Manders (proofs for the problems above were proposed also there).  </p>

<p>There are other such examples in "<a href="http://scholar.google.com/scholar?q=%22A%20Catalog%20of%20Complexity%20Classes%22&amp;um=1&amp;ie=UTF-8&amp;sa=N&amp;hl=en&amp;tab=ws">A Catalog of Complexity Classes</a>", but I haven't checked what is known about their NP-completeness under deterministic reductions.</p>

CC BY-SA 2.5
2011-02-09T10:07:01.953Z
2011-02-09T10:12:54.210Z
2011-02-09T10:12:54.210Z
Oleksandr Bondarenko
<p>In <a href="https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring">this question</a>, 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?</p>

CC BY-SA 2.5
2011-02-08T16:45:36.683Z
Unique SAT is $NP$-hard under randomized reduction.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-08T16:57:21.727Z
@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
CC BY-SA 2.5
2011-02-08T17:04:57.867Z
(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
CC BY-SA 2.5
2011-02-08T17:06:50.923Z
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 
CC BY-SA 2.5
2011-02-08T17:30:56.203Z
I just wanted to add that the shortest vector problem for LLL under $L_2$ norm for randomized reductions (paper by Ajtai [here](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.3023&rep=rep1&type=pdf)) 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
CC BY-SA 2.5
2011-02-08T17:54:45.780Z
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 
CC BY-SA 2.5
2011-02-08T18:53:46.830Z
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
CC BY-SA 2.5
2011-02-08T20:55:54.260Z
@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
CC BY-SA 2.5
2011-02-09T01:44:04.667Z
Why is everybody writing answers in comments? :P
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-09T04:08:46.550Z
@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
CC BY-SA 2.5
2011-02-09T04:35:05.907Z
@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
CC BY-SA 2.5
2011-02-10T19:37:18.193Z
@user834: Your comment really should be an answer. Do you want to post it as one?
Peter Shor 
<cc.complexity-theory><np-hardness><big-list><randomness><reductions>
Problems that are NP-complete under randomized or P/poly reductions.
Peter Shor 
# Problems that are NP-complete under randomized or P/poly reductions.

(Asked by: username_0 on 2011-02-08)

In [this question](https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring), 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?

**Tags:** cc.complexity-theory, np-hardness, big-list, randomness, reductions

> **Comments:**
> **username_1**: Unique SAT is $NP$-hard under randomized reduction.  
> **username_2**: @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.  
> **username_2**: (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.)  
> **username_0**: 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.  
> **username_3**: I just wanted to add that the shortest vector problem for LLL under $L_2$ norm for randomized reductions (paper by Ajtai [here](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.3023&rep=rep1&type=pdf)) 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.  
> **username_0**: 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.  
> **username_4**: 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).  
> **username_5**: @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.  
> **username_6**: Why is everybody writing answers in comments? :P  
> **username_2**: @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 username_0was looking for. Since Unambiguous SAT fits the bill, I assume that also means Unambiguous X fits whenever X is fairly natural.  
> **username_5**: @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.  
> **username_0**: @username_3: Your comment really should be an answer. Do you want to post it as one?  

---

## 3 answers

### Answer by username_4 on 2011-02-09. Score: 10 | Accepted answer

Under randomized reduction with probability $\frac{1}{2}$ (known also as [$\gamma$-reducibility](http://scholar.google.com/scholar?hl=en&q=%22gamma-reducibility%22&btnG=Search&as_sdt=1,5&as_ylo=&as_vis=0), on the discussion of randomized reductions see "[On Unique Satisfiability and Randomized Reductions](http://scholar.google.com/scholar?q=%22On%20unique%20satisfiability%20and%20randomized%20reductions%22&um=1&ie=UTF-8&sa=N&hl=en&tab=ws)") problems

1. [Linear divisibility](http://books.google.com/books?id=JogZAQAAIAAJ&q=%22linear+divisibility%22&dq=%22linear+divisibility%22&hl=en&ei=oVtSTYGlFIy28QPf9YmjCw&sa=X&oi=book_result&ct=result&resnum=22&ved=0CIcBEOgBMBU)
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](http://books.google.com/books?id=-X39_rA3VSQC&pg=PA90&dq=%22linear+divisibility%22&hl=en&ei=oVtSTYGlFIy28QPf9YmjCw&sa=X&oi=book_result&ct=result&resnum=11&ved=0CFQQ6AEwCg#v=onepage&q=%22linear%20divisibility%22&f=false)). $\gamma$-reducibility was introduced in the paper "[Reducibility, randomness, and intractibility](http://scholar.google.com/scholar?q=%22reducibility,+randomness,+and+intractibility%22+&hl=en&btnG=Search&as_sdt=1,5)" 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](http://scholar.google.com/scholar?q=%22A%20Catalog%20of%20Complexity%20Classes%22&um=1&ie=UTF-8&sa=N&hl=en&tab=ws)", but I haven't checked what is known about their NP-completeness under deterministic reductions.


---

### Answer by username_1 on 2011-02-09. Score: 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


---

### Answer by username_3 on 2011-02-24. Score: 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."](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.3023&rep=rep1&type=pdf) discusses complexity results of finding shortest vectors for lattice reduction using randomized reduction steps.


---

