Od dwóch dekad trwają fantastyczne prace nad Permanentnym. Przez pewien czas zastanawiałem się nad możliwością zastosowania algorytmu Smooth P dla Permanent of Nonnegative Matrices. Istnieje oczywiście słynny algorytm JSV, ale jest to fpras. Myśląc o innych pracach w ramach wygładzonej złożoności, silną wskazówką bycia w wygładzonym P było istnienie algorytmu fpras / Psuedopolynomial.
Czy są jakieś przeszkody dla nieujemnego stałego przebywania w wygładzonym P?
Z góry dziękuję
Zelah
Odpowiedzi:
Lipton (Nowe kierunki w testach, 1991) pokazał, że jeśli permanent jest łatwy dla większości matryc, to jest łatwy dla wszystkich matryc. Nie znam wersji online, ale wynik można znaleźć w wielu notatkach z wykładów, na przykład tutaj: http://www.cse.cuhk.edu.hk/~andrejb/courses/f07-80240233/notes/lec16.pdf Istnieją ulepszenia Gemmela i Sudanu (IPL 43 (4): 169-174. 1992). Tak więc permanent jest średnio trudny dla równomiernego rozkładu. W przypadku wygładzonego wielomianowego algorytmu czasowego musisz wybrać rozkład w taki sposób, aby ominąć tę średnią twardość przypadku.