# Why rectangle packing is NP-hard but maybe not in NP?

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?

• NP definitely doesn't include all decision problems. Only those than can be solved in polynomial-time by a nondeterministc Turing machine. May 12 at 7:24
• Oh thank you very much, but how can i understand the last sentence.
– Jxb
May 12 at 7:27

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.
• @Max arxiv.org/pdf/1704.06969.pdf Understanding the class $\exists \mathbb{R}$, and hard problems for this class could help. May 13 at 11:44