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

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

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

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