تالار گفتمان مانشت

اولین موضوع داغ مانشت رو در این‌باره مطرح می‌کنیم: به زودی یه متن کامل در مورد موضوعات داغ و شیوه‌های برگزاری آن خواهیم داشت. در پایان هر مطلب یک جواب به عنوان بهترین جواب انتخاب می‌شه( البته نیاز به برنامه نویسی و ... داره که ان شا الله رو به راهش می‌کنیم )

مبحث این هفته طراحی الگوریتم درباره NPهاست. همون طور که می‌دونید یکی از مباحث مهم در زمینه طراحی الگوریتم‌ها بحث‌های مربوط به پیچیدگی است. خوب سوال ما در این مورد هست که تفاوت NP-Hard و NP-Complete در چیست؟ البته دوستان قبل از توضیح سوال اندکی در مورد مفهوم NP هم بحث کنند بد نیست.


خلاصه‌ای از مطالب مطرح شده در دانش‌نامه مانشت وارد خواهد شد.

مفهوم NP-Complete برای اولین بار در سال ۱۹۷۱ توسط Stephen Cook در مقاله ای با عنوان " پیچیدگی تئوری اثبات رویه‌ها " معرفی شد . اما نکته جالب اینجاست که خود عبارت NP-Complete در هیچ جای مقاله استفاده نشده بود . در آن کنفرانس علوم کامپیوتر بحث و مناظره شدیدی بین دانشمندان علوم کامپیوتر بر سر اینکه آیا مسائل NP-Complete میتوانند در یک پیچیدگی زمانی چند جمله ای توسط ماشین تورینگ قطعی حل شوند یا نه در گرفت .
در آن کنفرانس آقای John Hopcroft همه‌ی اعضا را با توجه به اینکه هیچ کس اثبات رسمی برای ادعای خود نداشت‌، به این توافق رساند که این سوال را که آیا مسائل NP-Complete در پیچیدگی زمانی چند جمله ای قابل حل هستند یا نه را به زمان دیگری موکول کنند .
از آن زمان تا کنون هنوز هیچ فردی نتوانسته به طور قاطعانه ادعا کند که آیا مسائل NP-Complete در پیچیدگی زمانی چند جمله ای قابل هستند یا نه ؟ و این موضوع به یکی از بزرگترین مسائل حل نشده‌ی ریاضیات تبدیل شده است .
موسسه ریاضیات Clay پیشنهاد پاداش یک میلیون دلاری داده برای کسی که یک اثبات رسمی ارائه کند مبنی بر اینکه آیا P=NP یا P≠NP ؟
در تئوری پیچیدگی محاسباتی‌، کلاس پیچیدگی NP-Complete( به طور خلاصه NPC )‌، یکی از کلاس های مسائل تصمیم گیری است . یک مسئله تصمیم گیری مانند L ‌، NP-Complete است اگر در مجموعه‌ی مسائل NP باشد به طوری که هر راه حلی که برای مسئله‌ی تصمیم گیری میدهد دارای پیچیدگی زمانی چند جمله ای یا O(n^k) باشد . همچنین میتوان این مسئله را در حوزه NP-Hard در نیز در نظر گرفت اگر بتوان هر مسئله NP را با تغییر ورودی به L تبدیل کرد .

جمله آخرتون در مورد قابلیت تبدیل رو اصلاح کنید. البته پارسال یه اثبات مبنی بر اینکه P≠NP ارایه شد که درابتدا به نظر درست می‌اومد اما بعد از بررسی‌ها یه سری مشکلات در استدلالش پیدا شد.
ممنون بابت تاریخچه و مقدمات خوب ادامه بحث رو در مورد این نوع زبان‌ها از سر می‌گیریم.
برای شناخت مسایل NP-Complete معمولاً از کاهش استفاده می‌شود. کاهش یعنی چه؟ و چه طوری به ما در شناخت مسایل NP-Complete کمک می‌کنه؟

(23 تير 1390 03:04 ب.ظ)admin نوشته شده توسط: [ -> ]برای شناخت مسایل NP معمولاً از کاهش استفاده می‌شود. کاهش یعنی چه؟ و چه طوری به ما در شناخت مسایل NP کمک می‌کنه؟

کاهش دادن‌: روشی برای تبدیل یک مساله به مساله دیگری است به طوری که حل مساله دوم به حل مساله اولیه کمک می کند .
در نظریه محاسبه پذیری اگر A به B کاهش پذیر بوده و B تصمیم پذیر باشد آن گاه Aنیز تصمیم پذیر خواهد بود و برعکس .
فرضیه:
این مطلب در مورد مسائل NP هم میتونه صادق باشه اما عکسشا نمی دونم .
یعنی اگر NPA به NPB کاهش پذیر باشد و مسائل NPB حل شود مسائل NPA هم حل میشه .
البته این فرضیه نظر خودم بود از مطالبی که تو این زمینه خوندم و نمی دونم آقای دکتر چقدر میتونه تو این زمینه درست باشه .

(23 تير 1390 10:22 ب.ظ) نوشته شده توسط: [ -> ]در نظریه محاسبه پذیری اگر A به B کاهش پذیر بوده و B تصمیم پذیر باشد آن گاه Aنیز تصمیم پذیر خواهد بود و برعکس .

جمله رو این‌طوری اصلاح می‌کنیم:
در نظریه محاسبه پذیری اگر A به B در زمان چند جمله‌ای کاهش پذیر بوده و B تصمیم ناپذیر باشد آن گاه Aنیز تصمیم ناپذیر خواهد بود. و بالاعکسش هم درست نیست!

برای نشان دادن اینکه آیا یک مسئله NPC است یا نه از سه مفهوم کلیدی استفاده میکنیم:
مسائل تصمیم گیری در مقابل مسائل بهینه سازی و دیگری کاهش
توضیح در مورد دو مفهوم اول
بسیاری از مسائل مورد علاقه‌ی ما مسائل بهینه سازی هستند که در آنها به هر یک از راه حل های محتمل یک مقدار میدهیم و تلاش میکنیم راه حلی را با بهترین مقدار پیدا کنیم . برای مثال در مسئله‌ی " کوتاهترین مسیر " گراف بدون جهت G را داریم و میخواهیم مسیری از راس u تا v را پیدا کنیم که شامل کمترین لبه‌ها باشد .
NPC بودن به طور مستقیم در مسائل بهینه سازی به کار نمی رود بلکه در مسائل تصمیم گیری که در آنها جواب بله یا خیر است( یا به طور رسمی صفر یا یک )است به کار میرود.
بنابراین نشان دادن اینکه مسئله ایی NPC است یا نه ما را به ناحیه مسائل تصمیم گیری محدود میکند . جایی که ارتباط مناسبی بین مسائل بهینه سازی و تصمیم گیری وجود دارد . ما معمولاً میتونیم یک مسئله‌ی بهینه سازی رو با محدود کردن مقدار بهینه به شکل یک مسئله‌ی تصمیم گیری در آوریم . به عنوان مثال در مسئله‌ی کوتاهترین مسیر که یک گراف جهت دار G و دو راس u و v و مقدار k را به ما داده اند بررسی اینکه مسیری وجود دارد از u به v که شامل بیشترین لبه‌ها باشد .
ارتباط بین مسئله‌ی بهینه سازی و مسئله‌ی تصمیم گیری زمانی به درد می خورد که بخواهیم نشان دهیم مسئله‌ی بهینه سازی مورد بحث یک مسئله‌ی سخت( hard )است . این به این خاطر است که مسئله‌ی تصمیم گیری آسانتر به نظر میرسد یا در واقع سختتر نیست . به عنوان مثال ما میتوانیم مسئله‌ی کوتاهترین مسیر را حل کرده و تعداد لبه‌ها را در کوتاهترین مسیر پیدا شده با پارامتر k در مسئله‌ی تصمیم گیری مقایسه کنیم .
به عبارت دیگر اگر یک مسئله‌ی بهینه سازی ساده باشد مسئله‌ی تصمیم گیری مرتبط با آن هم به همان نسبت ساده خواهد بود .
همچنین اگر دلایلی داشته باشیم که یک مسئله‌ی تصمیم گیری سخت است دلایلی خواهیم داشت که مسئله‌ی بهینه سازی مرتبط با آن هم سخت خواهد بود .
توضیح در مورد مفهوم کاهش
ایده ایی که برای نشان دادن اینکه یک مسئله سخت‌تر یا آسان‌تر از مسئله‌ی دیگری نیست مطرح شد حتی زمانی که هر دو مسئله‌، مسئله‌ی تصمیم گیری باشند نیز به کار میرود . ما از این ایده برای اثبات تقریباً تمامی مسائل NPC استفاده میکنیم .
اجازه بدید یک مسئله‌ی تصمیم گیری مانند A را در نظر بگیریم که میخواهیم آن را در پیچیدگی زمانی چند جمله ای O(n^k) حل کنیم . ورودی را به یک مسئله‌ی خاص به عنوان " نمونه ای " از این مسئله فراخوانی میکنیم . به عنوان مثال در مسئله‌ی مسیر‌، یک نمونه می تواند یک گراف خاص G باشد با دو راس خاص u و v از G و مقداری مشخص برای پارامتر k . حال فرض میکنیم که یک مسئله‌ی تصمیم گیری دیگری داریم با نام B‌، و میدانیم که این مسئله راه حلی در پیچیدگی زمانی چند جمله ای دارد . در نهایت فرض میکنیم رویه ای داریم که هر یک از نمونه های a از مسئله‌ی A را به نمونه های b از مسئله‌ی B با خصوصیات زیر تبدیل میکند یا "کاهش میدهد" .
۱ – عملیات کاهش دارای پیچیدگی زمانی چند جمله ای است .
۲ – جواب های هر دو مسئله یکسان است . یعنی جواب مسئله‌ی a " بلی" است اگر و فقط اگر جواب مسئله‌ی b "بلی" باشد .
این رویه را الگوریتم کاهشی با پیچیدگی زمانی چندجمله ای می نامیم که روشی را برای حل مسئله‌ی A در پیچیدگی زمانی چند جمله ای فراهم میکند .
پس کلاً سه مرحله داریم:
۱ – نمونه‌ی a از مسئله‌ی A را با استفاده از "الگوریتم کاهشی" با پیچیدگی زمانی چند جمله ای به نمونه‌ی b از مسئله‌ی B تغییر شکل میدهیم .
۲ – الگوریتم کاهشی را بر روی نمونه‌ی b از مسئله B اجرا میکنیم .
۳ – از جوابی که برای b به دست آورده ایم به عنوان جوابی برای مسئله‌ی a استفاده میکنیم .
تا زمانی که هر یک از این مراحل دارای پیچیدگی زمانی چند جمله ای است هر سه مرحله با هم نیز دارای پیچیدگی زمانی چند جمله ای خواهد بود و می توانیم بگوییم که راهی با پیچیدگی زمانی چند جمله ای برای تصمیم گیری روی مسئله‌ی a پیدا کرده ایم .
به عبارت دیگر با " کاهش " مسئله‌ی A به مسئله‌ی B‌، ما از سادگی B برای اثبات سادگی A استفاده کرده ایم .

آقای دکتر اگه اشکالی در مطلب دیدید خوشحال میشم اگه تذکر بدید

ممنون ازآقای دکتر بخاطر ایجاد این تایپیک این مبحث شیرین ترین مبحث هایی که من میخوام پس از قبولی تو ارشد به خواست خدا در موردش بیشتر بدونم و حتما در این زمینه مطالعه میکنم . فکر میکنم تو این زمینه حدودا حداقل ۲ تا سوال توی کنکورارشد علوم کامپیوتر ازش میدن حداقل تو این چند سال اخیر که اینطور بوده .

یه سری مطلب انگلیسی در مورد NP-Complete ضمیمه کردم اما ترجمه اش با دوستان محترم .

(24 تير 1390 12:07 ق.ظ)admin نوشته شده توسط: [ -> ]

(23 تير 1390 10:22 ب.ظ) نوشته شده توسط: [ -> ]در نظریه محاسبه پذیری اگر A به B کاهش پذیر بوده و B تصمیم پذیر باشد آن گاه Aنیز تصمیم پذیر خواهد بود و برعکس .

جمله رو این‌طوری اصلاح می‌کنیم:
در نظریه محاسبه پذیری اگر A به B در زمان چند جمله‌ای کاهش پذیر بوده و B تصمیم ناپذیر باشد آن گاه Aنیز تصمیم ناپذیر خواهد بود. و بالاعکسش هم درست نیست!

سلام عذر میخوام من باید جمله را کامل مینوشتم .
جمله را کامل میکنیم:
در نظریه محاسبه پذیری اگر A به B کاهش پذیر بوده و B تصمیم پذیر باشد آن گاه Aنیز تصمیم پذیر خواهد بود .همین طوراگر A تصمیم پذیر نبوده و به B کاهش یابد، آنگاه B نیز تصمیم پذیر نخواهد بود . این نکته آخر کلید اثبات تصمیم پذیر بودن مسائل مختلفی می باشد .
کتاب مقدمه ای بر نظریه محاسبات( جلد اول )
انتشارات: دانشگاه یزد
نویسنده‌: مایکل سیپسر
ترجمه‌: دکتر محمدحسن شیرعلی شهرضا

با سلام:
اقای دکتر چرا این تا پیک ادامه پیدا نکرد ؟؟؟؟

۱. خوب کسی در مورد تفاوت NP-hard و NP-Complete بحث نکرد.

۲. یه سوال جدید هم دارم: به نظر شما آیا اگر P≠NP زبانی داریم که نه جز P باشه و نه جز NP-Complete؟


برای جواب دادن به سوال اول من بهتره به این قضیه فکر کنید که ما چه زمانی یه زبان رو NP-Complete می‌دونیم و آیا NP-Complete زیر مجموعه NP-hard است؟

برای جواب به سوال دوم بهتره به مقالات جدیدی که در زمینه NP-Intermediate وجود داره یه نگاهی بیاندازید.

در مورد سوال ۱:
NP-Hard مسائلی هستند که حداقل به سختی سخت ترین مسائل NP هستند، اما لزوما در NP نیستند. در واقع یک مسئله NP-Hard هست اگر و تنها اگر حداقل یک مسئله NP-Complete وجود داشته باشد که در زمان چندجمله ای به آن کاهش پیدا کند. مثلا Halting Problem یک مسئله NP-Hard است، چرا که SAT به آن در زمان چند جمله ای کاهش پیدا می کند. واضح هست که Halting Problem، یک مسئله NP نیست.
یک مسئله NP-Hard لزوما Undecidable هم نیست. مثلا اگر NP!=PSPACE مسئله TQBF یا QSAT یک مسئله NP-Hard است، اما در NP نیست.

در مورد سوال ۲:
این دسته از زبان‌ها همان طور که گفتید در NP-Intermediate هستند. البته هنوز یک مسئله طبیعی و قابل لمسی در این کلاس پیدا نشده ولی در خود معرفی و اثبات وجود کلاس NP-Intermediate (قضیه Lander) یک زبان از این نوع ساخته می شود.

(27 آذر 1390 11:39 ب.ظ)psps1368 نوشته شده توسط: [ -> ]البته هنوز یک مسئله طبیعی و قابل لمسی در این کلاس پیدا نشده

اتفاقاً پیدا شده. مثال:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(28 آذر 1390 12:00 ق.ظ)admin نوشته شده توسط: [ -> ]

(27 آذر 1390 11:39 ب.ظ)psps1368 نوشته شده توسط: [ -> ]البته هنوز یک مسئله طبیعی و قابل لمسی در این کلاس پیدا نشده

اتفاقاً پیدا شده. مثال:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

این مسائل ثابت نشده که در NP-Intermediate هستند. یعنی نه گفته شده که در P هستند و نه در NP-Complete. یعنی فعلا فرض میشه که در NP-Intermediate هستند. (مشکوک به NP-Intermediate هستند... (; )

خوب با فرض اینکه P مخالف NP احتمالاً می‌شه اثباتشون کرد. توی قضیه Lander یه زبان از روی SAT ساخته شده.

سلام
میشه به من کمک کنید
لطفایه نمونه مساله از Np-Hard برام مثال بزنید