patternMinor
Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded?
Viewed 0 times
thehardstronglyunaryinputencodedcompletedoeswhenproblems
Problem
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.
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.
Solution
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.
Context
StackExchange Computer Science Q#10563, answer score: 4
Revisions (0)
No revisions yet.