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

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

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