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



1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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