مسائل $A$ و $B$ به ترتیب زیر می‌باشند:

مسئله‌ی $A$:

ورودی: مجموعه‌ی $A=\{x_1,x_2,…,x_n\}$ از اعداد طبیعی.

سوال: آیا این مجموعه، زیرمجموعه‌ای مانند $S$ دارد که جمع اعضای آن دقیقا نصف جمع اعضای $A$ باشد؟

مسئله‌ی $B$:

ورودی: مجموعه‌ی $A=\{x_1,x_2,…,x_n\}$ از اعداد طبیعی و عدد طبیعی $M$.

سوال: آیا این مجموعه، زیرمجموعه‌ای مانند $S$ دارد که جمع اعضای آن دقیقا $M$ باشد؟

برای هیچ‌کدام از مسائل بالا تا به حال الگوریتمی با زمان چند جمله‌ای پیدا نشده است. ثابت کنید اگر برای مسئله‌ی $A$‌الگوریتمی با زمان چند جمله‌ای پیدا شود، برای مسئله‌ی $B$ نیز الگوریتمی با زمان چند جمله‌ای یافت می‌شود. به عبارت دیگر روشی ارائه دهید که در آن مثال از مسئله‌ی $B$ را تغییر دهید و از روی ورودی آن در زمان چند جمله‌ای یک ورودی برای مسئله‌ی $A$ بسازید به طوری که به کمک پاسخ الگوریتم مسئله‌ی $A$ بتوان جواب مسئله‌ی $B$ را پیدا کرد.

• سوال بعد
• سوال قبل