Definition
Instance Encoding
Let
be an instance space and a finite alphabet. An instance encoding is an injective, computable map together with a computable decoder defined on its image such that
The problem instance supplied to a machine is the finite string
, and its encoded length is Time complexity is measured against this length. Different encodings may therefore change a complexity bound, although polynomially related encodings preserve polynomial-time solvability.