مسائل A و B به ترتیب زیر میباشند:
مسئلهی A:
ورودی: مجموعهی A={x1,x2,…,xn} از اعداد طبیعی.
سوال: آیا این مجموعه، زیرمجموعهای مانند S دارد که جمع اعضای آن دقیقا نصف جمع اعضای A باشد؟
مسئلهی B:
ورودی: مجموعهی A={x1,x2,…,xn} از اعداد طبیعی و عدد طبیعی M.
سوال: آیا این مجموعه، زیرمجموعهای مانند S دارد که جمع اعضای آن دقیقا M باشد؟
برای هیچکدام از مسائل بالا تا به حال الگوریتمی با زمان چند جملهای پیدا نشده است. ثابت کنید اگر برای مسئلهی Aالگوریتمی با زمان چند جملهای پیدا شود، برای مسئلهی B نیز الگوریتمی با زمان چند جملهای یافت میشود. به عبارت دیگر روشی ارائه دهید که در آن مثال از مسئلهی B را تغییر دهید و از روی ورودی آن در زمان چند جملهای یک ورودی برای مسئلهی A بسازید به طوری که به کمک پاسخ الگوریتم مسئلهی A بتوان جواب مسئلهی B را پیدا کرد.