Complejidad lisa del permanente no negativo

Se ha realizado un trabajo fantástico en lo Permanente durante las últimas dos décadas. Me he estado preguntando por un tiempo sobre la posibilidad de un algoritmo Smooth P para el Permanente de Matrices No Negativas. Por supuesto, existe el famoso algoritmo JSV, pero este es un fpras. Pensando en otro trabajo dentro de Smoothed Complexity, un fuerte indicio de estar en Smoothed P fue la existencia de un algoritmo fpras / Psuedopolynomial.

¿Hay alguna obstrucción al ser permanente no negativo en P alisado?

Gracias por adelantado

Zelah

Lipton (New direction in testing, 1991) mostró que si el permanente es fácil para la mayoría de las matrices, entonces es fácil para todas las matrices. No conozco una versión en línea, pero puede encontrar el resultado en muchas notas de clase, por ejemplo aquí: http://www.cse.cuhk.edu.hk/~andrejb/courses/f07-80240233/notes/lec16.pdf Gemmel y Sudán han mejorado (IPL 43 (4): 169-174. 1992). Entonces, el permanente es difícil en promedio para la distribución uniforme. Para un algoritmo de tiempo polinómico suavizado, debe elegir la distribución de tal manera que se evite esta dureza de caso promedio.