<p>Integer programming is strongly NP-hard, thus integer programs can in general not be solved in pseudo-polynomial time. The result of Röglin and Vöcking 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.</p>

<p>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 Röglin, SODA 2014).</p>

CC BY-SA 3.0
2013-10-17T08:38:03.560Z
2013-10-17T08:38:03.560Z
Bodo Manthey
<p>I have been facinated by the extraordinary explosion in Smoothed Analysis and was struck by a assertion in the paper <a href="http://www.roeglin.org/publications/IPCO05.pdf">Smoothed Analysis of Integer Programming</a>. 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!</p>

<p>The question therefore is:</p>

<blockquote>
  <p>Does this carry over to other problems universally? In particular what are the constraints?</p>
</blockquote>

CC BY-SA 2.5
2011-03-23T11:09:33.770Z
Could you elaborate on what is meant by "polynomially bounded" in this context?
András Salamon
<cc.complexity-theory><smoothed-analysis>
Smoothed Analysis: If a Problem has Pseudopolynomial Complexity, is it in Smooth P?
Zelah 02
# Smoothed Analysis: If a Problem has Pseudopolynomial Complexity, is it in Smooth P?

(Asked by: username_0 on 2011-03-23)

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](http://www.roeglin.org/publications/IPCO05.pdf). 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?

**Tags:** cc.complexity-theory, smoothed-analysis
> **Comments:**
> **username_1**: Could you elaborate on what is meant by "polynomially bounded" in this context?  

---

## 1 answers

### Answer by username_2 on 2013-10-17. Score: 4 | Accepted answer

Integer programming is strongly NP-hard, thus integer programs can in general not be solved in pseudo-polynomial time. The result of Röglin and Vöcking 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 Röglin, SODA 2014).


---

