Editing Computational complexity theory (section)

===Representing problem instances===
When considering computational problems, a problem instance is a [[string (computer science)|string]] over an [[Alphabet (computer science)|alphabet]]. Usually, the alphabet is taken to be the binary alphabet (i.e., the set {0,1}), and thus the strings are [[bitstring]]s. As in a real-world [[computer]], mathematical objects other than bitstrings must be suitably encoded. For example, [[integer]]s can be represented in [[binary notation]], and [[graph (discrete mathematics)|graph]]s can be encoded directly via their [[adjacency matrix|adjacency matrices]], or by encoding their [[adjacency list]]s in binary.

Even though some proofs of complexity-theoretic theorems regularly assume some concrete choice of input encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding. This can be achieved by ensuring that different representations can be transformed into each other efficiently.