# Does $\mathcal{P}\neq \mathcal{NP}$ preclude the possibility that an NPC problem could have polynomial time algorithms on *almost* any input?

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?

• What do you mean by "almost any input"? Oct 8 at 17:20
• @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. Oct 8 at 17:26
• You might be interested in Impagliazzo's classic paper: stuff.mit.edu/afs/sipb/project/reading-group/past-readings/… Oct 8 at 18:14