Only if they're (i) conjectured hard instances (ii) for which we can verify that a given solution is indeed optimal. Which in many cases is itself is a Gödel prize worthy task.