I do not have too much background in complexity theory, so please feel free to let know if my question is ill defined.

My question is, does $\mathcal{P}\neq \mathcal{NP}$ preclude the possibility that an NPC problem could have polynomial time algorithms on almost any input?

I am thinking something along the lines of the simplex algorithm; while the simplex algorithm takes exponential time in worst case, its complexity is polynomial assuming smoothed analysis.

Is it possible that $\mathcal{P}\neq \mathcal{NP}$ and there exists a polynomial time algorithm $P$ for an NPC problem that, while is exponential in worst case, is "smoothed-polynomial"/polynomial on almost all inputs?

  • 1
    $\begingroup$ What do you mean by "almost any input"? $\endgroup$
    – nir shahar
    Oct 8, 2021 at 17:20
  • $\begingroup$ @nirshahar I am intentionally leaving it ambiguous to allow for a reasonable definition of "almost". For example in the case of smoothed analysis, it states that given an worst case input $I$ (that takes exponential time), if your perturb the input every so slightly with an epsilon noise, you get an input that the algorithm takes polynomial time to run on. So while the algorithm isn't polynomial in the worst case, it is still polynomial on "almost all inputs" in the smoothed-analysis class. $\endgroup$ Oct 8, 2021 at 17:26
  • 2
    $\begingroup$ You might be interested in Impagliazzo's classic paper: stuff.mit.edu/afs/sipb/project/reading-group/past-readings/… $\endgroup$ Oct 8, 2021 at 18:14

1 Answer 1


Russell Impagliazzo described five possible worlds in his classic paper A personal view of average-case complexity. In one of them, Heuristica, P is different from NP, but NP is easy on average (in some specific technical case).

Recent work in meta-complexity has been aiming at ruling out Heuristica. See for example recent work of Shuichi Hirahara.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.