Pseudo-polynomial time

In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input, but is exponential in the length of the input – the number of bits required to represent it.

An NP-complete problem with known pseudo-polynomial time algorithms is called weakly NP-complete. An NP-complete problem is called strongly NP-complete if it is proven that it cannot be solved by a pseudo-polynomial time algorithm unless P=NP. The strong/weak kinds of NP-hardness are defined analogously.

Consider the problem of testing whether a number n is prime, by naively checking whether no number in ${\displaystyle \{2,3,\dots ,{\sqrt {n}}\}}$ divides ${\displaystyle n}$ evenly. This approach can take up to ${\displaystyle {\sqrt {n}}-1}$ divisions, which is sub-linear in the value of n but exponential in the length of n (which is about ${\displaystyle \log(n)}$). For example, a number n slightly less than 10,000,000,000 would require up to approximately 100,000 divisions, even though the length of n is only 10 digits. Moreover one can easily write down an input (say, a 300-digit number) for which this algorithm is impractical. Since computational complexity measures difficulty with respect to the length of the (encoded) input, this naive algorithm is actually exponential. It is, however, pseudo-polynomial time.

...
Wikipedia