Jaka jest złożoność upakowania prostokąta, gdy dozwolone są obroty?

W zadaniu pakowania prostokąt, jeden dany zestaw prostokątów i prostokąt, R . Zadaniem jest znalezienie umieszczenie R 1 , ... , r n wewnątrz R takie, że żaden z n prostokąty pokrywają. Ogólnie, orientacja każdego prostokąta r i jest stała. Oznacza to, że prostokąty nie mogą być obracane. W tym przypadku wiadomo, że problem jest NP-zupełny (patrz np. Korp 2003 ).$\{r_1,\dots,r_n\}$$R$$r_1,\ldots,r_n$$R$$n$$r_i$

Jaka jest złożoność problemu upakowania prostokąta, jeśli prostokąty można obracać o stopni?$90$

Intuicyjnie zezwolenie na obracanie powinno tylko utrudnić problem, ponieważ najpierw należy wybrać orientację dla każdego prostokąta, a następnie rozwiązać problem pakowania bez rotacji. Ale dowód na twardość NP w przypadku braku obrotu jest redukcją w stosunku do pakowania bin i wydaje się, że krytycznie zależy od stałej orientacji każdego prostokąta w celu skonstruowania pojemników. Nie udało mi się znaleźć odpowiedniego dowodu twardości NP dla przypadku, w którym dozwolone są obroty.

Możemy zredukować problem pakowania bez obrotu do problemu pakowania dozwolonego przez obroty w następujący sposób. Weźmy przykład problemu braku obrotu. Pionowo skali całego instancję dwukrotnie iloraz najmniejszej szerokości każdego prostokąta R i podzielona przez wysokość pojemnika prostokąt R . (Ten stosunek ma wielomianową liczbę bitów, więc transformacja może być wykonana w czasie wielomianowym.) Każdy skalowany prostokąt r $(R, r_1, r_2, \dots, r_n)$$r_i$$R$ mieści się w skalowanym pojemniku R ' tylko w jego pierwotnej orientacji, więc dopuszczanie obrotów nie dodaje żadnych nowych rozwiązań.$r'\!\!_i$$R'$