Suppose we have a NP-Hard problem such as the k-col, which is meant to determine if a graph may be colored using at most k different colors.

Considering we model the k-col problem as a linear programming problem, then apply slightly random perturbations (Spielman and Teng - 2001) to the input tableau for the simplex algorithm as mentioned here, obtaining a problem very close to the original one:

  1. may it be solved in polynomial time ?
  2. in practice, may it be solved optimally for a huge graph (1k vertices or more) or would the solution be a near-optimum ?

PS: Please, note I have considered this before posting this question, however, I still didn't understand, therefore, I would like to see an answer in simpler words. In addition, I'm not sure if smoothed analysis is related to the questions I've asked.


I'm not exactly sure what algorithm you suggest, but in general it is known there are many NP-hard problems that are also NP-hard to approximate. So I don't think this line of attacking NP-hard problems is going to lead you to success in polynomial time.

I suggest looking through https://people.eecs.berkeley.edu/~luca/pcp/ if you are curious for more information in this direction.


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