How to prove that a problem is not smoothed-polynomial?

Question

Many research works use Smoothed analysis to prove that some NP-hard problems can actually be solved efficiently in typical cases. A different notion with a similar goal is Generic-case complexity.

Suppose I have a problem X for which I cannot find an algorithm that runs in smoothed-polynomial time, or in generic polynomial time. As an excuse for my failure, I want to prove that X does not have a smoothed-polynomial or a generic-polynomial time algorithm, unless P=NP. How can I do this?

I checked this paper on smoothed complexity theory (by Markus Blaser and @BodoManthey) and this report on generic case complexity. They provide notions of "smoothed reduction" between problems, and prove completeness of some problems. But, they do not relate these notions (as far as I understood) to NP.

What are examples of problems that provably do not have Smoothed or generic-case polynomial-time algorithms unless P=NP?

Answer 1

With respect to smoothed analysis, the only case that I am aware of is the paper by Beier and Vöcking (Typical Properties of Winners and Losers in Discrete Optimization. SIAM J. Comput. 35(4): 855-881, 2006). They show that an optimization problem has polynomial smoothed complexity if and only if it has a randomized pseudo-polynomial-time algorithm.

This implies that problems that are strongly NP-hard, such as TSP, cannot be solved in smoothed polynomial time, unless P=NP.

Apart from this, most smoothed analysis results are about the performance of specific algorithms, not about the (smoothed) complexity of problems.