سوال ۲۱

دو مسئله‌ی زیر را در نظر بگیرید:

• مسئله‌ی کوله‌پشتی: یک کوله‌پشتی به حجم $M$ داریم (که $M$ می‌تواند خیلی خیلی بزرگ و حتی ناصحیح باشد!). $n$ کیسه به حجم‌های $v_1$ تا $v_n$ نیز به ما داده شده است. می‌خواهیم بدانیم آیا زیرمجموعه‌ای از کیسه‌ها وجود دارد که مجموع حجم‌های کیسه‌های آن دقیقاً برابر $M$ باشد و کیسه را کاملاً پر کند یا نه؟ دقّت کنید که در یک زیر مجموعه، هر عضو حداکثر یک‌بار می‌آید.
• مسئله‌ی پازل: یک جدول $k$ سطری و $k$ ستونی از خانه‌های $1\times 1$ داریم. $k^2$ تا شکل نیز به ما داده شده است که هر شکل از تعدادی خانه‌ی $1\times 1$ به‌هم‌چسبیده تشکیل شده (دو خانه به‌هم چسبیده‌اند اگر و فقط اگر در یک پاره‌خط به‌طول $1$ اشتراک داشته باشند؛ از این رو هرشکل،«یک تکّه» است) و مساحت هر شکل حداکثر $k^2$ است. می‌خواهیم بدانیم آیا می‌توان تمام جدول را با زیرمجموعه‌ای از این اشکال پوشاند یا نه؟ پوشش جدول به معنی قرار دادن تعدادی از اشکال موجود روی خانه‌های جدول است که هر خانه‌ی جدول دقیقاً و به‌طور کامل زیر یکی از اشکال باشد. دقّت کنید که از هر شکل حداکثر یک‌بار می‌توانیم استفاده کنیم و در این یک بار می‌توانیم شکل را بچرخانیم یا حتی دوران بدهیم. برای مثال شکل روبه‌رو را به $8$ طریق می‌توان در جدول قرار داد.

فرض کنید یک ماشین جادویی اختراع شده که مسئله‌ی کوله‌پشتی را در زمان چندجمله‌ای برحسب $n$ حل می‌کند (روایتی از این مسئله که به‌صورت داینامیک حل می‌شود چند جمله‌ای بر حسب $M$ و $n$ است؛ نه فقط بر حسب $n$). ثابت کنید می‌توان با استفاده از این ماشین، مسئله‌ی پازل را نیز در زمان چند جمله‌ای برحسب $k$ حل کرد.