Reibungslose Komplexität der nichtnegativen bleibenden Karte

In den letzten zwei Jahrzehnten wurde fantastisch an der Permanenten gearbeitet. Ich habe mich eine Weile über die Möglichkeit eines Smooth-P-Algorithmus für die Permanente von nichtnegativen Matrizen gewundert. Es gibt natürlich den berühmten JSV-Algorithmus, aber das ist ein fpras. Wenn man an andere Arbeiten in Smoothed Complexity denkt, war die Existenz eines fpras / Psuedopolynomial-Algorithmus ein deutlicher Hinweis darauf, dass man sich in Smoothed P befindet.

Gibt es irgendwelche Hindernisse für das nichtnegative bleibende Wesen in geglättetem P?

Danke im Voraus

Zelah

Lipton (New directions in testing, 1991) hat gezeigt, dass, wenn die bleibende Farbe für die meisten Matrizen einfach ist, es für alle Matrizen einfach ist. Ich kenne keine Online-Version, aber das Ergebnis finden Sie in vielen Vorlesungsskripten, zum Beispiel hier: http://www.cse.cuhk.edu.hk/~andrejb/courses/f07-80240233/notes/lec16.pdf Es gibt Verbesserungen von Gemmel und Sudan (IPL 43 (4): 169-174. 1992). So ist die dauerhafte Verteilung im Durchschnitt für die gleichmäßige Verteilung schwer. Für einen geglätteten polynomiellen Zeitalgorithmus müssen Sie die Verteilung so wählen, dass diese Durchschnittshärte umgangen wird.