  Difficult, in particular NP-complete, optimization problems are traditionally
solved approximately using search heuristics. These are usually slowed down by
the rugged landscapes encountered, because local minima arrest the search
process. Cover-encoding maps were devised to circumvent this problem by
transforming the original landscape to one that is free of local minima and
enriched in near-optimal solutions. By definition, these involve the mapping of
the original (larger) search space into smaller subspaces, by processes that
typically amount to a form of coarse-graining. In this paper, we explore the
details of this coarse-graining using formal arguments, as well as concrete
examples of cover-encoding maps, that are investigated analytically as well as
computationally. Our results strongly suggest that the coarse-graining involved
in cover-encoding maps bears a strong resemblance to that encountered in
renormalisation group schemes. Given the apparently disparate nature of these
two formalisms, these strong similarities are rather startling, and suggest
deep mathematical underpinnings that await further exploration.
