- شروع کننده موضوع
- #1
tiberium
کاربر فوق‌حرفه‌ای
- ارسال‌ها
- 1,057
- امتیاز
- 1,052
- نام مرکز سمپاد
- شهید بهشتی سمنان
- شهر
- سمنان
- سال فارغ التحصیلی
- 1389
- مدال المپیاد
- المپیاد کامپیوتر
- دانشگاه
- صنعتی شریف
- رشته دانشگاه
- مهندسی فن آوری اطلاعات
به زبان خیلی ساده یه سری مسایل هستن که نمیشه برای اونها الگوریتم چند جمله ای ارائه کرد.
مثلا حل سودوکو چیزیه که الگوریتم چند جمله ای نداره
یا مثلا اینکه آیا یک گراف دور همیلتونی داره یا نه
یه مساله معروف دیگش مساله subset sum هست
مسالش اینه که ما n تا عدد داریم. می خوایم بدونیم آیا میشه یه عده از اینا رو انتخاب کرد که جمعشون دقیقا بشه K یا نه.
این مساله همه NP هست .یعنی الگوریتم چند جمله ای براش وجود نداره و مجبوریم یه جورایی همه حالات و چک کنیم.
یعنی باید به عبارتی جمع تمام زیر مجموعه های این n تا عدد رو بدست بیاریم و با k مقایسه کنیم. یعنی حدود 2 به توان n عملیات
که مبینید یه عدد توانی(نمایی) هست.
یه دانش مندی ثابت کرده که مساله ی SAT (اگر خواستین خودتون راجع بهش بخونید) np هست.
حالا یکی از کارهایی که میشه کرد نبدیل مسایل به مسایل NP هست.
یه وقت هست بهتون میگن باید ثابت کنید که این مساله الگوریتم چند جمله ای نداره و NP هست.
برای ثابت کردن این مسایل باید سعی کنید مساله رو جوری به مسایل NP دیگه مربوط کنید طوری که بگید اگر من بتونم برای این مساله الگوریتم چند جمله ای بیارم با استفاده از همین الگوریتم میتونم اون مساله ی NP رو هم حل کنم.پس چون اون مساله NP هستش قطعا الگوریتم من نمیتونه چند جمله ای باشه. پس مساله من هم NP هست.
جالبه که بدونید همه مسایل NP به هم قابل تبدیلن...بعنی میشه با هر کدوم اون یکی رو حل کرد . و اگر یه روزی بتونن برا یکی از اینا الگوریتم چند جمله ای بیارن کل مسایل NP حل میشه. و به عبارتی درس خوندن و دانشگاه رفتن ما و این حرفا همه الکی میشه
یعنی الان این مساله هنوز open هست که آیا p=np?
و فکر کنم جایزه 1 میلیون دلاری داره حل این سوال!
البته حدسی که زدن نه هست
حالا جالب اینه که مثلا نوشتن paper از طرف کامپیوتر np هست. یعنی اگر مسایل NP حل بشن دیگه میبینید خود کامپیوتر میتونه علم تولید کنه تو زمان چمد جمله ای...و این یعنی بیکار شدن همه آدما.
حالا اول از همه فرض می کنیم مسایل زیر NP هستن
وجود دور همیلتونی در یک گراف.
وجود مسیر همیلتونی در یک گراف
مساله subset sum
فعلا همینا کافیه. حالا مساله اول
ثابت کنید این مساله NP هست
گراف ساده و بدون جهت G رو داریم. می خوایم بدونیم آیا دوری تو این گراف وجود داره که حداقل از نصف راس ها رد بشه.(دیگه به تکراری نبودن و ایناش هم دقت کنید که نمی خوایم از رو یه راس 2 بار رد بشیم.)
مثلا حل سودوکو چیزیه که الگوریتم چند جمله ای نداره
یا مثلا اینکه آیا یک گراف دور همیلتونی داره یا نه
یه مساله معروف دیگش مساله subset sum هست
مسالش اینه که ما n تا عدد داریم. می خوایم بدونیم آیا میشه یه عده از اینا رو انتخاب کرد که جمعشون دقیقا بشه K یا نه.
این مساله همه NP هست .یعنی الگوریتم چند جمله ای براش وجود نداره و مجبوریم یه جورایی همه حالات و چک کنیم.
یعنی باید به عبارتی جمع تمام زیر مجموعه های این n تا عدد رو بدست بیاریم و با k مقایسه کنیم. یعنی حدود 2 به توان n عملیات
که مبینید یه عدد توانی(نمایی) هست.
یه دانش مندی ثابت کرده که مساله ی SAT (اگر خواستین خودتون راجع بهش بخونید) np هست.
حالا یکی از کارهایی که میشه کرد نبدیل مسایل به مسایل NP هست.
یه وقت هست بهتون میگن باید ثابت کنید که این مساله الگوریتم چند جمله ای نداره و NP هست.
برای ثابت کردن این مسایل باید سعی کنید مساله رو جوری به مسایل NP دیگه مربوط کنید طوری که بگید اگر من بتونم برای این مساله الگوریتم چند جمله ای بیارم با استفاده از همین الگوریتم میتونم اون مساله ی NP رو هم حل کنم.پس چون اون مساله NP هستش قطعا الگوریتم من نمیتونه چند جمله ای باشه. پس مساله من هم NP هست.
جالبه که بدونید همه مسایل NP به هم قابل تبدیلن...بعنی میشه با هر کدوم اون یکی رو حل کرد . و اگر یه روزی بتونن برا یکی از اینا الگوریتم چند جمله ای بیارن کل مسایل NP حل میشه. و به عبارتی درس خوندن و دانشگاه رفتن ما و این حرفا همه الکی میشه
یعنی الان این مساله هنوز open هست که آیا p=np?
و فکر کنم جایزه 1 میلیون دلاری داره حل این سوال!
البته حدسی که زدن نه هست
حالا جالب اینه که مثلا نوشتن paper از طرف کامپیوتر np هست.
یعنی اگر مسایل NP حل بشن دیگه میبینید خود کامپیوتر میتونه علم تولید کنه تو زمان چمد جمله ای...و این یعنی بیکار شدن همه آدما.حالا اول از همه فرض می کنیم مسایل زیر NP هستن
وجود دور همیلتونی در یک گراف.
وجود مسیر همیلتونی در یک گراف
مساله subset sum
فعلا همینا کافیه. حالا مساله اول
ثابت کنید این مساله NP هست
گراف ساده و بدون جهت G رو داریم. می خوایم بدونیم آیا دوری تو این گراف وجود داره که حداقل از نصف راس ها رد بشه.(دیگه به تکراری نبودن و ایناش هم دقت کنید که نمی خوایم از رو یه راس 2 بار رد بشیم.)
الگوریتم