Does the difficulty of a strongly NP-hard or NP-complete problem (as e.g. defined here) change when its input is unary instead of binary encoded?
What difference does it make if the input of a strongly NP-hard problem is unary encoded? I mean, if I take for instance the weakly NP-complete Knapsack problem, it is NP-complete when binary encoded but can be solved in polynomial time by dynamic programming when unary encoded. Maybe it has some implications for hardness of higher levels of the polynomial time heirarchy?
Does the notion of strongly ...-hard also hold for other complexity classes, e.g. higher classes of the polynomial time hierarchy?
I previously asked this question at stackoverflow.com but it was pointed out that it is more appropriate here.