نشریه دانشکده کامپیوتر دانشگاه صنعتی اصفهان
زندگی سخته(گذری بر مسئله‌هایP و NP)
به قلم محمد روغنی ورودی ۹۷ کارشناسی مهندسی کامپیوتر دانشگاه صنعتی اصفهان
فرض کنین یه روز بامزه پاییزی تو خونتون نشستین و دارین از یه فنجون قهوه لذت می‌برین که یهو یادتون می‌افته دو تا از میان‌ترم‌هاتون تداخل داره. آخه مگه برنامه‌ریزی یه سری امتحان، طوری که با هم تلاقی نداشته باشن، چه قدر می‌تونه سخت باشه؟
جواب کوتاهش اینه که هنوز کسی نمی‌دونه! D:
امروز می‌خوایم با هم درباره یکی از بنیادی‌ترین مسئله‌های علوم کامپیوتر و ریاضیات صحبت کنیم.
مسئله P vs. NP …
بیاین یکم به عقب برگردیم زمانی که اولین کامپیوتر‌ها ساخته شده بودن:
مهندس‌ها خیلی خوشحال و خندان مشغول حل کردن مسئله‌هایی هستن که قبلا مجبور بودن با دست حلشون کنن (بالاخره کی دوست داره یک معادله رو توی سه دقیقه حل کنه وقتی می‌تونه ۳ هفته وقت بذاره تا یه کامپیوتر لامپی رو برنامه نویسی کنه؟). خیلی زود همه فهمیدن که یک سری از مسئله‌ها به قدری حل شدنشون زمان می‌بره که عملا هیچ‌وقت تموم نمیشن :( بیاین به این مسئله‌ها بگیم مسئله‌های سخت! هر از چندگاهی یک نفر برای یکی از این مسئله‌های سخت یک راه‌حل هوشمندانه پیدا می‌کرد. اما یه سری از مسئله‌ها بودند که هر چقدر ملت تو سر خودشون می‌زدن باز هم راه‌حل سریع‌تر براشون پیدا نمی‌شد.
خب اینجا بود که P و NP مطرح شد. به مسئله‌هایی که برای پیدا کردن جوابشون یک راه‌حل سریع وجود داره میگیم عضو کلاس P هستن؛ بعد کلاس NP یک کلاس بزرگ‌تر و دربردارنده P هست که دسته‌ای از مسئله‌هاست که اگر جوابشون رو داشته باشیم می‌تونیم سریع چک کنیم که آیا جواب درسته یا نه؛ مثلا اگر به شما یک برنامه از امتحانات کل دانشگاه رو بدن می‌تونین سریع چک کنین که آیا دانشجویی وجود داره که به فنا رفته باشه یا نه. دقت کنین برای مسئله‌ای که عضو کلاس NP باشه ولی عضو کلاس P نباشه؛ فقط جوابشو میشه سریع چک کرد و اگر سعی کنین که جوابش رو خودتون پیدا کنین احتمالا وقت زیادی ازتون می‌گیره. البته از وقت زیاد منظورم چند صد هزار سال یا حتی بیشتره :)
همون طور که احتمالا خودتون متوجه شدین اکثر مسئله‌های جذاب و بامزه‌ای که ما باهاشون سر و کله می‌زنیم مثل برنامه‌ریزی، طراحی مدار و دیتابیس‌ها و تاشدگی پروتئین که باهاش میشه سرطان رو درمان کرد همه NP هستن.
خب احتمالا الان براتون سوال پیش اومده که اگر این مسئله‌ها او‌ن‌قدر سخت هستن پس چطوری حلشون می‌کنیم؟ داستان از این قراره که درسته ما معمولا جواب دقیق یا بهینه‌ی این مسئله‌ها رو نمی‌تونیم توی مدت زمان قابل قبولی پیدا کنیم، اما خیلی از اون‌ها نمونه‌های ساده شده‌ای دارن که میشه سریع‌تر حلشون کرد و از قضا توی دنیای واقعی اون نمونه‌های خاص زیاد اتفاق می‌افتن. توی خیلی از مواقع دیگر ما از الگوریتم‌های تقریبی استفاده می‌کنیم. در واقع درسته که نمی‌تونیم جواب اصلی مسئله رو پیدا کنیم ولی سعی می‌کنیم که یک جواب نسبتا خوب براش پیدا کنیم. مثلا توی برنامه‌ریزی امتحانات سعی می‌کنیم استراتژی‌ای رو انتخاب کنیم که احتمال به وجود اومدن تداخل کم باشه.
خلاصه هر از چندگاهی ملت می‌فهمیدن که یک سری از مسئله‌هایی که قبلا فکر می‌کردن NP هستن در واقع عضو P بودن ولی هنوز راه‌حل مناسبی براشون پیدا نکرده بودن. این جا بود که دانشمندان به این فکر افتادن که آیا P و NP برابرن یا نه؟ به عبارت دیگه، اگر درستی یک جواب رو بتونیم سریع چک کنیم، می‌تونیم سریع هم پیداش کنیم؟
مسئله P vs. NP دنبال اینه که بفهمه آیا همه مسئله‌های NP عضو P هم هستن یا واقعا یک سری از مسئله‌های NP وجود دارن که از اون‌هایی که داخل P هستن، سخت‌ترن. اگر همه مسئله‌های NP واقعا عضو P باشن خیلی از مسئله‌هایی که ما فکر می‌کنیم سختن برای کامپیوتر راحت از آب در میان مثلا چیزهایی مربوط به زیست‌شناسی، اقتصاد و حتی درمان سرطان یا کرونا …
قبل از اینکه ادامه بدیم بیاین ببینیم که دقیقا منظور ما از سریع چیه!
خب P مخفف Polynomial Time هست؛ یعنی یک مسئله‌ی عضو P رو می‌تونیم داخل زمانی که یک تابع چندجملهای از اندازه ورودیش حل میشه، حل کنیم. NP هم مخفف Non-Deterministic Polynomial هست و از نظر عملی میشه گفت، اگر راهی بود که بی‌نهایت کامپیوتر هم‌زمان تمام راه‌حل‌های ممکن رو چک کنن، اون مسئله در زمان چندجملهای حل میشد.
حالا داستان جایی جالب میشه که اوایل دهه ۷۰ میلادی دانشمندان فهمیدن که تعداد زیادی از مسئله‌هایی که داخل NP هستن، در واقع یک مسئله واحدن. حالا اگر یک نفر موفق به حل کردن یکی از اون‌ها توی زمان چندجملهای بشه همه مسئله‌های NP رو میشه با استفاده از همون راه‌حل تو زمان چندجملهای حل کرد که به اون مسئله‌ها NP-Complete میگیم. مثلا متوجه شدن که حل کردن سریع سودوکو(که NP-Complete هست) باعث شکستن رمزنگاری سیستم بانک‌ها میشه! چون اغلب الگوریتم‌های رمزنگاری بر پایه یک مسئله NP هستن. (مانند الگوریتم RSA[1] که بر پایه تجزیه اعداد به فاکتورهای اوله)
نکته بامزه اینه که استنتاج در حالت کلی خودش یه مسئله NP-Hard (مسائلی که حداقل به سختی مسائل NP-Complete باشن) هست! پس اثبات کردن اینکه P = NP هست یا نه خودش یه مسئله سخته. یا شایدم آسون!
امروزه اکثر دانشمندان علوم کامپیوتر بر این باورن که P = NP نیست و منطقشون هم اینه که کلی آدم خبره به کلی از این مسئله‌ها که همشون ذاتا یک مسئله هستن، کلی فکر کردن و هیچ‌کس برای هیچ کدومشون راه‌حل سریع پیدا نکرده.
اسکات آرونسون [2]نظر خودش رو درباره‌ی این مسئله این‌طوری میگه:
If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.
سوالی که ممکنه بعد خوندن این متن براتون پیش بیاد اینه که اگه P = NP باشه که خب خیلی بی‌مزه میشه و دیگه اصلا مسئله سختی باقی نمی‌مونه. نکته اینه که P وNP کلاس‌های کوچکی از دنیای همه مسائلن و واقعیت اینه که مسئله‌های خیلی‌خیلی زیادی وجود داره که حتی از اونایی که داخل NP هستن هم سخت‌ترن. مثلا پیدا کردن استراتژی برد در بازی شطرنج یه نمونه از این مسئله‌هاست. ممکنه ما هنوز درصد خیلی بالایی از اون مسئله‌ها رو به خاطر دانش محدودمون اصلا باهاش مواجه نشده باشیم.
*اسپویلر!!
در آخر می‌خوام به پایان سریال سیلیکون ولی [3] اشاره کنم که یک برنامه نوشتن که به صورت اتفاقی رمزنگاری‌های پیچیده رو خیلی سریع می‌شکوند و گفتن ما یک هیولا خلق کردیم. احتمالاً بعد از خوندن این متن متوجه شدین که برنامه‌ای که توانایی حل کردن همچین مسئله‌هایی رو داشته باشه، در واقع یک پیشرفت خیلی بزرگ علمیه. به عبارت دیگه داشتن همچین برنامه‌ای کمک خیلی بزرگی به درمان بیماری سرطان میکنه؛ و شاید اگر همچین چیزی وجود داشت، خیلی زود میشد کرونا رو ریشه‌کن کرد.
امیدوارم از این متن لذت برده باشین. حتماً نظراتتون رو توی کامنت برامون بنویسین.
پانویس ها:
[1] RSA algorithm
[2] Scott Aaronson
[3] Silicon Valley
مطلبی دیگر از این انتشارات
عادت‌های ما
مطلبی دیگر از این انتشارات
چرا داوطلبانه فعالیت می‌کنم؟!
مطلبی دیگر از این انتشارات
از هوشمندی تا هوشیاری