Weakly NP-complete problems and strongly NP-complete problems
Many problems involve integers, for example in the form of integer weights. There are two common ways to encode integers:


Binary encoding, or more generally base B encoding for some constant B.
Unary encoding, in which (ignoring signs) $n \geq 0$ is encoded as $0^n1$.


A problem is weakly NP-complete if it is NP-complete when weights are encoded in binary. It is strongly NP-complete if it is NP-complete when weights are encoded in unary. For example, SUBSET SUM is weakly NP-complete but not strongly NP-complete, whereas BIN PACKING is strongly NP-complete.

Every strongly NP-complete problem is also weakly NP-complete since the reduction which changes the encoding of integers from unary to binary runs in polynomial time. The reduction in the other direction, in contrast, could run in exponential time.

Primality testing can be done in polynomial time in both unary and binary encodings, though in the latter case it's a highly non-trivial result known as the AKS primality test.