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

• مسئله‌ی کوله‌پشتی‎:‎ یک کوله‌پشتی به حجم ‎$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$ حل کرد.

• سوال قبل