۰
subtitle
ارسال: #۱
کاهش پذیری چند جمله ای
اگه A<B باشه :
اگه B ان پی هارد باشه اونوقت A ؛ nph میتونه باشه ؟
Aباید سختیش اندازه Bیا شل تر از B باشه دیگه؟A اینجا p و npc و npهم میتونه باشه؟ اینا سخت تر از nph که نیستن ؟
بعد اگهB ؛ npcباشه A میتونه NPCو P باشه؟ NPH نمیتونه باشه؟ Npچی میتونه باشه؟
اگه B ان پی هارد باشه اونوقت A ؛ nph میتونه باشه ؟
Aباید سختیش اندازه Bیا شل تر از B باشه دیگه؟A اینجا p و npc و npهم میتونه باشه؟ اینا سخت تر از nph که نیستن ؟
بعد اگهB ؛ npcباشه A میتونه NPCو P باشه؟ NPH نمیتونه باشه؟ Npچی میتونه باشه؟
۰
ارسال: #۲
RE: کاهش پذیری چند جمله ای
(۰۵ اردیبهشت ۱۳۹۶ ۰۵:۴۷ ب.ظ)*tarannom* نوشته شده توسط: اگه A<B باشه :
اگه B ان پی هارد باشه اونوقت A ؛ nph میتونه باشه ؟
Aباید سختیش اندازه Bیا شل تر از B باشه دیگه؟A اینجا p و npc و npهم میتونه باشه؟ اینا سخت تر از nph که نیستن ؟
بعد اگهB ؛ npcباشه A میتونه NPCو P باشه؟ NPH نمیتونه باشه؟ Npچی میتونه باشه؟
اگه B ان پی هارد باشه اونوقت A ؛ nph میتونه باشه ؟
پاسخ : بله A میتونه NP-Hard هم باشه
Aباید سختیش اندازه Bیا شل تر از B باشه دیگه؟A اینجا p و npc و npهم میتونه باشه؟ اینا سخت تر از nph که نیستن ؟
پاسخ : بله باید سختیش کوچکتر یا مساوی B باشه ، پس A میتونه NP-Hard یا NP باشه وقتی NP میتونه باشه پس P , NP-Complete هم میتونه باشه
بعد اگهB ؛ npcباشه A میتونه NPCو P باشه؟ NPH نمیتونه باشه؟ Npچی میتونه باشه؟
پاسخ : A نمیتونه NP-Hard باشه ولی NP میتونه باشه پس NP , NP-Comlete هم میتونه باشه
۰
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close