می‌خواهیم ‎$n$‎ کار ‎$j_1,j_2,...,j_n$‎ را بر روی یک پردازنده انجام دهیم. زمان لازم برای انجام هر کار یک واحد است. برای هر کار تعدادی بازه داریم که باید آن کار را در یکی از آن بازه‌ها انجام دهیم. طول تمامی این بازه‌ها و زمان شروع و پایان آن‌ها عددی صحیح است. می‌توانیم انتخاب کنیم که یک کار را در چه زمانی انجام دهیم، ولی بایستی زمان انجام یک کار در یکی از بازه‌های مربوط به آن قرار گیرد.

می‌دانیم که پردازنده نمی‌تواند دو کار را به صورت همزمان انجام دهد. هنگامی که پردازنده می‌خواهد کاری انجام دهد باید روشن شود. هنگامی که پردازنده کاری را به پایان رساند، اگر کاری دیگری باید در همان لحظه شروع شود، اجرای آن را شروع می‌کند. در غیر این صورت پردازنده به طور خودکار خاموش می‌شود.

هدف ما در این مسئله این است که همه‌ی کارها را انجام دهیم به طوری که تعداد دفعاتی که مجبور می‌شویم پردازنده را روشن کنیم کمینه شود.

مسئله‌ی ‎$A$‎

می‌دانیم که تعداد بازه‌های مربوط به هر کار حداکثر ‎$2$‎ است.

مسئله‌ی ‎$B$‎

می‌دانیم که تعداد بازه‌های مربوط به هر کار حداکثر ‎$2$‎ است و طول هر یک از این دو بازه، ‎$1$‎ واحد زمانی است.

مسئله‌ی ‎$C$‎

می‌دانیم که بازه‌های مربوط به کارها همگی مجزا هستند.(یعنی هیچ دو بازه‌ای از هیچ دو کاری اشتراک ندارند‎(.‎

مسئله‌ی ‎$D$

مسئله در حالت کلی.(هیچ محدودیتی روی طول و تعداد بازه‌ها وجود ندارد‎(.‎ ‎

1. ثابت کنید که اگر الگوریتمی با زمان چندجمله‌ای وجود داشته‌باشد که مسئله‌ی ‎$A$‎ را حل کند، الگوریتمی با زمان چندجمله‌‌ای برای مسئله‌ی ‎$D$‎ نیز وجود دارد‎.
2. ثابت کنید که اگر الگوریتمی با زمان چندجمله‌ای وجود داشته‌باشد که مسئله‌ی ‎$C$‎ را حل کند، الگوریتمی با زمان چندجمله‌ای برای مسئله‌ی ‎$B$‎ نیز وجود دارد‎.
3. ثابت کنید که اگر الگوریتمی با زمان چندجمله‌ای وجود داشته‌باشد که مسئله‌ی ‎$B$‎ را حل کند، الگوریتمی با زمان چندجمله‌ای برای مسئله‌ی ‎$C$‎ نیز وجود دارد‎.

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