Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded?
A problem size of $N$ encoded in unary is size $N$ and $\log N$ if binary. If the time taken is $F(N)$, this is $F(\text{size})$ in the first case and $F(2^{\text{size}})$ in the second case. So an algorithm that is polynomial for the first case will probably be exponential for the second. The encoding of the problem can so change the complexity of an algorithm radically.