  Hard combinatorial optimization problems deal with the search for the minimum
cost solutions (ground states) of discrete systems under strong constraints. A
transformation of state variables may enhance computational tractability. It
has been argued that these state encodings are to be chosen invertible to
retain the original size of the state space. Here we show how redundant
non-invertible encodings enhance optimization by enriching the density of
low-energy states. In addition, smooth landscapes may be established on encoded
state spaces to guide local search dynamics towards the ground state.
