  We study the existence of approximate pure Nash equilibria ($\alpha$-PNE) in
weighted atomic congestion games with polynomial cost functions of maximum
degree $d$. Previously it was known that $d$-approximate equilibria always
exist, while nonexistence was established only for small constants, namely for
$1.153$-PNE. We improve significantly upon this gap, proving that such games in
general do not have $\tilde{\Theta}(\sqrt{d})$-approximate PNE, which provides
the first super-constant lower bound.
  Furthermore, we provide a black-box gap-introducing method of combining such
nonexistence results with a specific circuit gadget, in order to derive
NP-completeness of the decision version of the problem. In particular,
deploying this technique we are able to show that deciding whether a weighted
congestion game has an $\tilde{O}(\sqrt{d})$-PNE is NP-complete. Previous
hardness results were known only for the special case of exact equilibria and
arbitrary cost functions.
  The circuit gadget is of independent interest and it allows us to also prove
hardness for a variety of problems related to the complexity of PNE in
congestion games. For example, we demonstrate that the question of existence of
$\alpha$-PNE in which a certain set of players plays a specific strategy
profile is NP-hard for any $\alpha < 3^{d/2}$, even for unweighted congestion
games.
  Finally, we study the existence of approximate equilibria in weighted
congestion games with general (nondecreasing) costs, as a function of the
number of players $n$. We show that $n$-PNE always exist, matched by an almost
tight nonexistence bound of $\tilde\Theta(n)$ which we can again transform into
an NP-completeness proof for the decision problem.
