[theory students] what is a reasonable encoding?

[Eric Bach <bach@xxxxxxxxxxx>]

I'm about to do NP-completeness in 520.  There is always
the presumption that mathematical objects (sets, graphs,
numbers, ...) are encoded "reasonably".  But what does
that mean?

One way to handle this is to define "standard" encodings,
and then say an encoding is reasonable if there are
poly-time translations (forward and back) to the standard
ones.  But this seems arbitrary, and therefore unsatisfactory.

I'd say that information theory gives a necessary condition
for an encoding to be reasonable.  But that isn't sufficient,
as there might be a really weird (even non-computable) dictionary
between my encoding and the standard one.

Have you ever seen a formal treatment of this question?

Eric