سلام
یکی از معمول ترین روشها برای اثبات NP-hard بودن یک مسئله استفاده از reduction in polynomial time to another np-hard problem هست. این به این معنیه که شما کافیه ثابت کنید که اون مسئله با استفاده از یه الگوریتم دلخواه در زمان polynomial به یکی از مسائل NP-hard شناخته شده تبدیل میشه. بعنوان مثال مسئله برای اثبات NP-hard بودن مسئله کوله پشتی (knapsack problem) کافیه که به هر کدوم از آیتمها یک متغیر boolean اختصاص بدین که فقط میتونه مقدار 0 یا 1 رو بگیره(X1,X2,...). بعد حجم کوله پشتی رو بصورت ثابت C در نظر میگیرید که بنابراین میتونید شرط کوله پشتی رو بصورت X1 + X2 + ... + Xn =< C بنویسید. حالا این دقیقا یه مسئله برنامه ریزی خطی هست که NP-hard بودن اون برای نمونه های دارای متغیرهای باینری (مثل همین مسئله) قبلا اثبات شده.
امیدوارم مفید بوده باشه.
|