# Is it possible to approximate the solution of NP-Hard problems in polynomial time using linear programming? [closed]

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.