====== کاغذ ======
دو مسئلهٔ زیر را در نظر بگیرید:

  - گراف ‎$G$‎ و دو رأس ‎$s$‎ و ‎$t$‎ از آن داده شده است. تعدادی مهره روی بعضی از رئوس ‎$G$‎ وجود دارد. می‌خواهیم مهره‌ها را طوری برروی یال‌ها حرکت دهیم که در پایان، یک مسیر مانند ‎$p$‎ از ‎$s$‎ تا ‎$t$‎ ایجاد شود که هر رأس ‎$p$‎ دارای دست‌کم یک مهره باشد. هدف این است که طی این عملیات بیش‌ترین میزان حرکت یک مهره کمینه شود. مثلاً اگر یک مهره دو واحد حرکت کند و دیگری سه واحد، کمیتی که می‌خواهیم کمینه کنیم سه می‌باشد.
  - گراف ‎$G$‎ داده شده است. می‌خواهیم بدانیم که آیا ‎$G$‎ یک مسیر همیلتونی دارد یا خیر؛  مسیر همیلتونی مسیری ‎$n$‎ رأسی است، اگر ‎$n$‎ تعداد رئوس گراف باشد.


ثابت کنید که اگر مسئله‌ی ‎«۱»‎ الگوریتمی چندجمله‌ای داشته باشد، مسئله‌ی ‎«۲»‎ نیز الگوریتمی چندجمله‌ای خواهد داشت.

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