9
$\begingroup$

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?

enter image description here

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

1 Answer 1

Reset to default
17
$\begingroup$

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).

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Thank you very much, the main reason is the arbitary rotation right? What if we restrict the minim rotation angle, and any rotation must be multiple of minimum rotation angle. Is it NP in this situation? $\endgroup$
    – Jxb
    May 12 at 8:05
  • 6
    $\begingroup$ If you change the problem so that it has a polynomial size certificate which can be verified in polynomial time, then it is in NP. $\endgroup$
    – Yuval Filmus
    May 12 at 8:06
  • 3
    $\begingroup$ @Max arxiv.org/pdf/1704.06969.pdf Understanding the class $\exists \mathbb{R}$, and hard problems for this class could help. $\endgroup$
    – Narek Bojikian
    May 13 at 11:44
  • 5
    $\begingroup$ @Max The numbers could be irrational numbers, or perhaps arbitrarily complicated ratios. Who says they are a polynomial number of bits long? $\endgroup$
    – user253751
    May 13 at 11:59
  • 3
    $\begingroup$ @Max Actually, since you specified a rotation matrix, in almost all cases 4n of the 6n numbers would be irrational with your idea - infinity bits long. How do you verify infinity bits in finite time? $\endgroup$
    – user253751
    May 13 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.