patternModerate
Why rectangle packing is NP-hard but maybe not in NP?
Viewed 0 times
whyrectanglebuthardpackingmaybenot
Problem
Recently I studied a MIT open course.
In lecture2, it is stated that Rectangle Packing is NP-hard.
I can understand this because the problem can be reduced to 3-partition problem
But I don't know why it's an open problem whether it's in NP.
In lecture2 it is stated that:
it is complicated to encode rotations efficiently.
My question:
How to understand the last sentence?
In lecture2, it is stated that Rectangle Packing is NP-hard.
I can understand this because the problem can be reduced to 3-partition problem
But I don't know why it's an open problem whether it's in NP.
In lecture2 it is stated that:
it is complicated to encode rotations efficiently.
My question:
How to understand the last sentence?
Solution
In order for a language $L$ to be in NP, there needs to be a way to certify that instance $x$ belongs to $L$. This "way" is a polynomial size witness which can be verified in polynomial time.
In this case, the obvious witness is a packing of the rectangles. Given such a packing, it is easy to check that it is indeed a packing. What is less clear is whether the witness has polynomial size, since it is not clear how to encode the rotations succinctly (or at all).
In this case, the obvious witness is a packing of the rectangles. Given such a packing, it is easy to check that it is indeed a packing. What is less clear is whether the witness has polynomial size, since it is not clear how to encode the rotations succinctly (or at all).
Context
StackExchange Computer Science Q#151483, answer score: 17
Revisions (0)
No revisions yet.