Analiza wygładzona: jeśli problem ma złożoność pseudopolinomialną, czy jest on płynny?

Zafascynowała mnie niezwykła eksplozja w analizie wygładzonej i uderzyło mnie stwierdzenie w artykule Analiza wygładzonego programowania liczb całkowitych . Stwierdzono, że programowanie liniowe w liczbach całkowitych jest wygładzone P, jeśli jest ograniczone wielomianowo. Było to niezbędne, ponieważ programowanie liczb całkowitych jest pseudo-wielomianowe!

Pytanie zatem brzmi:

Czy to uniwersalnie przenosi się na inne problemy? W szczególności jakie są ograniczenia?

Programowanie liczb całkowitych jest silnie trudne dla NP, dlatego programów liczb całkowitych zasadniczo nie można rozwiązać w czasie pseudo-wielomianowym. Wynik Röglina i Vöckinga jest taki, że pod warunkiem, że zakres liczb całkowitych, które mogą przyjmować zmienne, jest wielomianowo ograniczony, (losowo) pseudopoliminalna rozwiązywalność jest równoważna wielomianowej wygładzonej złożoności. Zatem ogólne programy liczb całkowitych nie mają wygładzonej wielomianowej złożoności.

Stwierdzenie „losowa złożoność pseudo-wielomianowa = złożoność wygładzona wielomianowo” ogólnie nie jest prawdą. Na przykład heurystyka odwrotna dla Max-Cut działa w czasie pseudo-wielomianowym, ale nie jest znane, czy lokalne optymalne w odniesieniu do heurystyki odwróconej można znaleźć z wielomianową wygładzoną złożonością (porównaj Etscheid i Röglin, SODA 2014).