a problem encoding
Before we can ask 'how long does it take?' we have to agree on what counts as the input and how it is written down. A computer does not see 'the number seventeen' or 'this graph' directly; it sees a string of symbols — bits, or characters on a tape. A problem encoding is the agreed recipe for turning a real object (a number, a graph, a list of jobs) into such a string, and for reading a string back as the object. It is the bridge between the abstract problem and the concrete bytes an algorithm actually chews on.
Why fuss over this? Because the SIZE of the input — the thing we measure running time against — depends on the encoding, and a sloppy choice can lie to us. Take an integer N. If you write it in binary (or decimal), it takes about log N digits, so its input size is about log N. If you instead write it in 'unary' as N tally marks, its size is N, exponentially larger. An algorithm that loops N times looks 'linear in the input' under the unary encoding but 'exponential in the input' under the binary encoding — same algorithm, opposite verdict. The honest convention in this whole subject is the natural, concise binary encoding: numbers in binary, graphs as adjacency lists or matrices, and so on, so that the input size grows like the information content, not like the value.
The good news is that for the questions we care about, the exact encoding rarely matters as long as it is 'reasonable'. Binary versus decimal versus an adjacency-list-versus-matrix choice differ only by a polynomial factor, so whether a problem is solvable in polynomial time does not change. The encodings to AVOID are the pathological ones, above all unary numbers, which artificially inflate the input size and can make a genuinely hard problem look easy. Whenever you read 'input size n' or 'polynomial time', a sensible binary-style encoding is being assumed underneath.
Consider 'is N prime?'. Trial division up to sqrt(N) does about sqrt(N) work. With N written in binary, the input size is k = log2(N) bits, so sqrt(N) = 2^(k/2) — exponential in the input size! That is why naive trial division is NOT a polynomial-time primality test. The verdict flips only because we measure against the binary input length, the honest encoding.
Input size is the encoded length, not the numeric value — sqrt(N) is exponential in log N.
The classic trap is unary encoding. A 'pseudo-polynomial' algorithm (like the O(nW) knapsack DP) looks polynomial only when its numbers are treated as if written in unary; in the honest binary encoding W is exponential in its bit length, so the algorithm is not truly polynomial-time.