<p>Lipton (New directions in testing, 1991) showed that if the permanent is easy 
for most matrices, then it is easy for all matrices. I do not know an online version but you can find the result in many lecture notes, for instance here:
<a href="http://www.cse.cuhk.edu.hk/~andrejb/courses/f07-80240233/notes/lec16.pdf">http://www.cse.cuhk.edu.hk/~andrejb/courses/f07-80240233/notes/lec16.pdf</a>
There are improvements by Gemmel and Sudan (IPL 43(4): 169-174. 1992).
So the permanent is hard on the average for the uniform distribution.
For a smoothed polynomial time algorithm you have to choose the distribution in such a way that this average-case hardness is circumvented.</p>

CC BY-SA 3.0
2013-03-22T20:06:42.087Z
2013-03-22T20:06:42.087Z
Markus Bläser
<p>There has been fantastic work done on the Permanent going on for the last two decades.I have been wondering for a while about the possibility of a Smooth P algorithm for the Permanent of Nonnegative Matrices. There is of course the famous JSV algorithm but this is a fpras. Thinking about other work within Smoothed Complexity, a strong hint of being in Smoothed P was the existence of a fpras / Psuedopolynomial algorithm. </p>

<p>Are there any obstructions to the Nonnegative Permanent being in Smoothed P?</p>

<p>Thanks in advance</p>

<p>Zelah</p>

<cc.complexity-theory><complexity-classes>
Smooth Complexity of the Nonnegative Permanent
Zelah 02
# Smooth Complexity of the Nonnegative Permanent

(Asked by: username_0 on 2013-03-21)

There has been fantastic work done on the Permanent going on for the last two decades.I have been wondering for a while about the possibility of a Smooth P algorithm for the Permanent of Nonnegative Matrices. There is of course the famous JSV algorithm but this is a fpras. Thinking about other work within Smoothed Complexity, a strong hint of being in Smoothed P was the existence of a fpras / Psuedopolynomial algorithm.

Are there any obstructions to the Nonnegative Permanent being in Smoothed P?

Thanks in advance

Zelah

**Tags:** cc.complexity-theory, complexity-classes

---

## 1 answers

### Answer by username_1 on 2013-03-22. Score: 13 | Accepted answer

Lipton (New directions in testing, 1991) showed that if the permanent is easy
for most matrices, then it is easy for all matrices. I do not know an online version but you can find the result in many lecture notes, for instance here:
<http://www.cse.cuhk.edu.hk/~andrejb/courses/f07-80240233/notes/lec16.pdf>
There are improvements by Gemmel and Sudan (IPL 43(4): 169-174. 1992).
So the permanent is hard on the average for the uniform distribution.
For a smoothed polynomial time algorithm you have to choose the distribution in such a way that this average-case hardness is circumvented.


---

