Traveling salesperson (TSP) : Given a map with n cities ,find the shortest possible routes that visits all cities exactly once and terminates at the origin city.
TSP :
nb cities to visit : n^2 pairwise city distances
efficiently -> n!
description size grows faster than linear with the problem size
Alphabets
an alphabet is finit and nonempty set of symbols -> binary {0,1}
Strings and lengths
A string over an alphabet is a finite sequence of symbols drawn from the alphabet. The length is the total number of symbols it contains.
Bit enconding
every symbol from a given alphabet can be represented as a bitstring. This representation is one-to-one and only scales logartihmically in alphabet size
