تاپيک: اثبات np-hard
نمايش پست تنها
قديمي ۰۳-۳۰-۱۳۸۹, ۰۲:۴۱ قبل از ظهر   #2 (لینک دائم)
alijy Male
Super Moderator
 
آواتار alijy
 
تاريخ عضويت: خرداد ۱۳۸۹
محل سكونت: ارض الله الواسعة
پست ها: 78
تشكرها: 23
250 تشكر در 77 پست
My Mood: Khonsard
پيش فرض

سلام
یکی از معمول ترین روشها برای اثبات 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 بودن اون برای نمونه های دارای متغیرهای باینری (مثل همین مسئله) قبلا اثبات شده.
امیدوارم مفید بوده باشه.
alijy آفلاين است   پاسخ با نقل قول
از alijy تشكر كرده اند:
Astaraki (۰۳-۳۰-۱۳۸۹), neda2 (۰۳-۳۰-۱۳۸۹)