  The Metropolis process (MP) and Simulated Annealing (SA) are stochastic local
search heuristics that are often used in solving combinatorial optimization
problems. Despite significant interest, there are very few theoretical results
regarding the quality of approximation obtained by MP and SA (with polynomially
many iterations) for NP-hard optimization problems.
  We provide rigorous lower bounds for MP and SA with respect to the classical
maximum independent set problem when the algorithms are initialized from the
empty set. We establish the existence of a family of graphs for which both MP
and SA fail to find approximate solutions in polynomial time. More
specifically, we show that for any $\varepsilon \in (0,1)$ there are $n$-vertex
graphs for which the probability SA (when limited to polynomially many
iterations) will approximate the optimal solution within ratio
$\Omega\left(\frac{1}{n^{1-\varepsilon}}\right)$ is exponentially small. Our
lower bounds extend to graphs of constant average degree $d$, illustrating the
failure of MP to achieve an approximation ratio of $\Omega\left(\frac{\log
(d)}{d}\right)$ in polynomial time. In some cases, our impossibility results
also go beyond Simulated Annealing and apply even when the temperature is
chosen adaptively. Finally, we prove time lower bounds when the inputs to these
algorithms are bipartite graphs, and even trees, which are known to admit
polynomial-time algorithms for the independent set problem.
