skip to content

Why can the same amount-scanning routine count as polynomial time under one input encoding and exponential under another?

level: middleimportance: should knowfreq 44%

answer

  1. the yardstick is part of the question
  2. tally marks make the input as big as the number
  3. any base of two or more is equivalent
  4. reasonable encodings are polynomially related
  5. padding would buy tractability for free

basics

~20 s

Because the encoding fixes what the input length is. Written in tally marks, a value of one million is a million symbols long, so a per-unit scan is linear; written in any base of two or more it is twenty bits, and the same scan is exponential.

solid answer

~40 s

Complexity is a function of `n`, and `n` only exists once you have said how the instance is written down. In unary — a value of V as V tally marks — the description is as long as the number is large, so a routine doing one step per unit is linear in `n` and therefore polynomial. In binary, decimal or hexadecimal, the description is about `log V` symbols and the same routine is exponential in `n`. The convention is to admit only *reasonable* encodings: those that are polynomially related to one another, which every base of two or more is. Unary is not — it is exponentially longer — so it is excluded, because otherwise padding the input would buy a tractability claim that no algorithm earned.

code

pseudocode · 10 lines
pseudocode
// an amount supplied in unary: "||||" means four

function total_units(input):
    count = 0
    for each mark in input:       // one pass over the symbols
        count = count + 1
    return count

// linear in the INPUT LENGTH - but the input is as long
// as the amount is large, so nothing was made cheaper

go deeper

for a junior

Take away one sentence: the same routine can look efficient or hopeless depending on how the input is written down, because the written form is what the bound is measured against.

for a middle

Explain the length relation — tally marks give a length equal to the value, positional notation gives a length near its logarithm — and say why bases two, ten and sixteen are interchangeable while unary is not.

for a senior

Use this in review: when a complexity claim arrives, restate it as polynomial in the bits of the real instance before accepting it, and be alert to bounds that only hold because the yardstick was inflated.

for a principal

The point worth defending is that a definition satisfiable by padding the input measures nothing. Reasonable-encoding closure is what makes complexity claims portable between teams that store the same data differently.

## No instance has a size until you fix an encoding A bound of `c * n^k` is meaningless until `n` is defined, and `n` is the number of symbols in the instance's written description. That means the description convention is part of the problem statement, not a detail of how it happens to be stored. Change the convention and you change `n`, which can change the verdict on an algorithm whose code did not change at all. This is not a puzzle or a trick; it is the reason complexity theory bothers to say 'under a reasonable encoding' in its definitions. ## Unary against the positional notations **Unary** writes a value of `V` as `V` copies of a single symbol — a tally. **Positional** notations write `V` in about `log_b(V)` symbols for base `b`. | encoding | how one million is written | length | cost of a one-step-per-unit scan, measured in n | |---|---|---|---| | unary | a million tally marks | 1,000,000 symbols | linear in n | | decimal | 1000000 | 7 digits | exponential in n | | binary | 11110100001001000000 | 20 bits | exponential in n | The routine is identical in all three rows. What moved is the denominator: in the unary row, the input is already as large as the work, so the work is proportional to the input; in the other two rows, the input is logarithmically small and the work is exponential in it. ## Why padding is not a proof of efficiency If unary counted as a legitimate encoding, the following recipe would 'prove' any magnitude-driven algorithm efficient: 1. Take a routine whose cost tracks the numeric values it is given. 2. Insist the numbers be supplied in tally marks. 3. Observe that the cost is now linear in the input length. 4. Declare the algorithm polynomial-time. Nothing about the computation improved. The only thing that changed is that the instance was inflated until the work looked small beside it. A definition that can be satisfied by padding the input tells you nothing about the algorithm, so the definition rules the padding out rather than accepting the conclusion. ## Which encodings the definition accepts The standard is that two encodings are interchangeable when each can be converted to the other in polynomial time and the lengths are polynomially related. Under that standard: - **Every base of two or more is fine.** Base two, ten and sixteen differ in length by constant factors, so a polynomial bound under one is a polynomial bound under all. Base ten to base two is a factor of about 3.3. - **The usual structure encodings are fine.** A graph written as an adjacency matrix and the same graph written as an edge list are polynomially related, so membership in the polynomial-time class does not depend on which you pick — even though a particular algorithm's exponent may. - **Unary is not fine.** Its length is exponential in the length of any positional encoding of the same value, which is precisely the relation the standard excludes. - **Nor is any compression that makes the description exponentially shorter**, for the mirror-image reason: it can make an easy routine look impossibly hard by shrinking the yardstick. ## The honest use of unary Unary is excluded as the default encoding, but a statement about unary-encoded input is still a meaningful statement, and a useful one. Saying 'this problem is solvable in polynomial time when its numbers are supplied in unary' is a real result: it says the difficulty lives entirely in the magnitudes, not in the combinatorial structure. That is a sharper and more informative claim than 'the algorithm is slow', and it is why the distinction is kept rather than waved away. ## What to say when this comes up in review When someone claims a routine is polynomial, the question that settles it is: *polynomial in what, written how?* If the claim survives being restated as 'polynomial in the number of bits of the file, with the amounts in ordinary positional notation', it is a real claim. If it only survives when the numbers are imagined as counts of units, the claim was an artefact of the yardstick rather than a property of the algorithm.

  • Why are base two and base ten treated as the same encoding for this purpose?
    Their lengths differ by a constant factor of about 3.3, and converting between them takes polynomial time. A bound that is a polynomial in one length is therefore a polynomial in the other, so no problem changes class. Only an encoding whose length is exponentially different — such as unary — can move the verdict.
  • Is a claim stated about unary-encoded numbers ever worth making?
    Yes. Saying a problem is solvable in polynomial time when its numbers arrive in unary says the hardness lives in the magnitudes rather than in the combinatorial structure, which is genuinely informative. What is not allowed is using that statement as evidence that the problem is tractable under ordinary positional input.

saying these in an interview costs you the question

  • Thinks the input length is a property of the numbers alone.
  • Claims switching from decimal to binary can change the class.
  • Accepts a unary-encoded input as a normal instance description.
  • Says the encoding only affects constant factors, never the class.
  • Believes a compressed description gives the same length for complexity purposes.