I have been facinated by the extraordinary explosion in Smoothed Analysis and was struck by a assertion in the paper Smoothed Analysis of Integer Programming. This stated that Integer Linear Programming is in Smoothed P if Polynomially Bounded. This was essential true by the virtue that Integer Programming is Pseudo-polynomial!The question therefore is:Does this carry over to other problems universally? In particular what are the constraints?
Smoothed Analysis: If a Problem has Pseudopolynomial Complexity, is it in Smooth P?
cc.complexity theory;smoothed analysis
Integer programming is strongly NP-hard, thus integer programs can in general not be solved in pseudo-polynomial time. The result of Rglin and Vcking is that, provided that the range of integers that the variables can assume is polynomially bounded, (randomized) pseudo-polynomial solvability is equivalent to polynomial smoothed complexity. Thus, general integer programs do not have polynomial smoothed complexity.The statement randomized pseudo-polynomial complexity = polynomial smoothed complexity is not known to be true in general. For instance, the flip heuristic for Max-Cut runs in pseudo-polynomial time, but it is unknown if a local optimum w.r.t. the flip heuristic can be found with polynomial smoothed complexity (cf. Etscheid and Rglin, SODA 2014).