====== سوال ۱۰ ======


مسائل $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$ را پیدا کرد.


  * [[سوال ۱۱|سوال بعد]]
  * [[سوال ۹|سوال قبل]]