<p>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.</p>
<p>This implies that problems that are strongly NP-hard, such as TSP, cannot be solved in smoothed polynomial time, unless P=NP.</p>
<p>Apart from this, most smoothed analysis results are about the performance of specific algorithms, not about the (smoothed) complexity of problems.</p>

CC BY-SA 4.0
2024-06-25T14:20:53.537Z
2024-06-25T14:20:53.537Z
Bodo Manthey
<p>Many research works use <a href="https://en.wikipedia.org/wiki/Smoothed_analysis" rel="nofollow noreferrer">Smoothed analysis</a> to prove that some NP-hard problems can actually be solved efficiently in typical cases. A different notion with a similar goal is <a href="https://en.wikipedia.org/wiki/Generic-case_complexity" rel="nofollow noreferrer">Generic-case complexity</a>.</p>
<p>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?</p>
<p>I checked this <a href="https://link.springer.com/chapter/10.1007/978-3-642-32589-2_20" rel="nofollow noreferrer">paper on smoothed complexity theory</a> (by Markus Blaser and @BodoManthey) and this <a href="http://www.stevens.edu/algebraic/Files/GC/gc_survey.pdf" rel="nofollow noreferrer">report on generic case complexity</a>. They provide notions of &quot;smoothed reduction&quot; between problems, and prove completeness of some problems. But, they do not relate these notions (as far as I understood) to NP.</p>
<p>What are examples of problems that provably do not have Smoothed or generic-case polynomial-time algorithms unless P=NP?</p>

<cc.complexity-theory><np-hardness><reductions><smoothed-analysis>
How to prove that a problem is not smoothed-polynomial?
Erel Segal-Halevi
# How to prove that a problem is not smoothed-polynomial?

(Asked by: username_0 on 2024-05-31)

Many research works use [Smoothed analysis](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](https://link.springer.com/chapter/10.1007/978-3-642-32589-2_20) (by Markus Blaser and @BodoManthey) and this [report on generic case complexity](http://www.stevens.edu/algebraic/Files/GC/gc_survey.pdf). 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?

**Tags:** cc.complexity-theory, np-hardness, reductions, smoothed-analysis

---

## 1 answers

### Answer by username_1 on 2024-06-25. Score: 6 | Accepted answer

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.


---

