Weakly NP-complete problems and strongly NP-complete problems

Question

I'm still confused with the terms Weakly NP-complete and strongly NP-complete. Many people states that weakly NP-complete problems are the problems with time complexity growing as a polynomial in the magnitude of the input, while strongly NP-complete problems are the problems with time complexity growing as a polynomial in the size of the input.
Does this make checking whether a number is prime or not (which is always considered as polynomial-time problem) a weakly NP-complete problem since its time complexity is growing as a polynomial in the magnitude of the input but as an exponential in the size of the input?

Answer 1

Many problems involve integers, for example in the form of integer weights. There are two common ways to encode integers:

1. Binary encoding, or more generally base B encoding for some constant B.
2. 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.