NP-hardness and "reasonable encodings"

(You can watch the video version of this post on YouTube.)

One thing I always enjoy pointing out is that NP-hardness … is about Turing machines. It’s about symbols on tapes, and uh, state transitions and moving heads. I mean, there are shortcuts to thinking about this that are basically equivalent in all the ways that we care about, but here’s a formal “implementation detail” – so to speak – that kind of leaks out of the definition. The way that we normally specify problems, we say, oh, the input is a graph (for example) uh, and then, does this graph have a Hamiltonian cycle?

UNDIRECTED HAMILTON CIRCUIT
INPUT: graph G
PROPERTY: G has a cycle which includes each node exactly once.

What about the tape of my Turing machine, though? How is this graph represented? What is the alphabet of symbols and how long is the description of this graph? Because we’re supposed to give a runtime bound in terms of the length of the input. What is this length? And the answer is .. hhm, we don’t really care. We’ll just just give the bound in terms of the number of vertices, or edges, or .. whatever. And then we talk about something like “reasonable encodings.” To say that this Hamiltonian cycle problem over here is NP-complete is to say: there exists a reasonable way to encode graphs onto a Turing-machine input tape, such that the problem of recognising representations of Hamiltonian graphs … is NP-complete. And for NP-completeness we don’t care about polynomial factors, so it’s probably fine - uh, maybe we could do an adjacency matrix, or adjacency lists - though it’s actually a little bit tricky to say how long that representation is with arbitrarily large graphs and only a finite alphabet, but up to polynomial factors it’s all good.

But you have to be .. a little bit careful. Here’s a question: what is a “reasonable encoding” of unbounded natural numbers? Maybe for the problem: Given a number $n$, is it prime?

PRIME
INPUT: integer n
PROPERTY: n is prime

This is not NP-complete - well, probably not: there’s a polynomial time algorithm, so that would be surprising. But: polynomial in what? How do we encode the instance? How do we write $n$ .. on the tape of a Turing machine?

Well, I guess we write it in binary. That seems .. reasonable, and yeah, that is how you do that. But then in a certain number of symbols, I can encode an exponentially large number. The length of the instance is: $\log(n)$. So what you call a polynomial time algorithm, for primality testing, should be polynomial in … $\log(n)$. Simply trying all divisors takes exponential time, in the length of the instance.

And what this means, is that if the input to your problem has numbers. you have to be a little bit careful about what the size if your instance actually is, because maybe there’s might be an exponential difference there, and that might influence NP-hardness. This leads to the concepts of “strong” and “weak” NP-hardness, as well as the concept of “pseudopolynomial itme,” which we might talk about another time.