15

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

Community
  • 1
Zelah 02
  • 1,578
  • 7
  • 16

1 Answers1

13

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.

Markus Bläser
  • 2,938
  • 18
  • 19