این محقق در حال توسعه ابزار جدیدی برای درک مسائل محاسباتی دشوار است که غیرقابل حل به نظر می رسد
این ایده که برخی از مسائل محاسباتی در ریاضیات و علوم کامپیوتر می تواند دشوار باشد، جای تعجب ندارد. در واقع، یک دسته کامل از مسائل وجود دارد که حل آنها از نظر الگوریتمی غیرممکن در نظر گرفته می شود. درست در زیر این کلاس، چند مشکل "آسان" وجود دارد که کمتر درک شده اند - و ممکن است امکان پذیر نباشند.
دیوید گامارنیک، پروفسور تحقیقات عملیاتی در دانشکده مدیریت اسلون MIT و موسسه داده‌ها، سیستم‌ها و جامعه، بر جدیدترین و کمتر مطالعه‌شده‌ترین موضوعاتی تمرکز می‌کند که بیشتر به دنیای روزمره مرتبط هستند، زیرا شامل شانس هستند - یکی از ویژگی‌های جدایی ناپذیر از سیستم های طبیعی او و همکارانش ابزار قدرتمندی را برای تجزیه و تحلیل این مشکلات ایجاد کرده اند که ویژگی همپوشانی شکاف (یا OGP) نام دارد. گامارنیک روش جدید را در مقاله‌ای که اخیراً در این مقاله منتشر کرده است، تشریح کرد اطلاعیه های آکادمی ملی علوم.
P NP
پنجاه سال پیش، معروف ترین مسئله در علم کامپیوتر نظری فرموله شد. با برچسب "P ≠ NP"، او می پرسد که آیا مشکلات مربوط به مجموعه داده های عظیمی وجود دارد که پاسخ آنها را می توان نسبتاً سریع تأیید کرد، اما راه حل آنها - حتی اگر بر روی سریع ترین رایانه های موجود توسعه یابد - زمان زیادی طول می کشد.
فرض P ≠ NP هنوز اثبات نشده است، اما اکثر دانشمندان کامپیوتر معتقدند که بسیاری از مشکلات شناخته شده - از جمله، برای مثال، مشکل فروشنده دوره گرد - در این دسته فوق العاده دشوار قرار می گیرند. چالشی که در مثال با فروشنده وجود دارد، یافتن کوتاه ترین مسیر، از نظر مسافت یا زمان، از طریق N شهر مختلف است. مدیریت این کار زمانی که N = 4 باشد آسان است، زیرا تنها شش مسیر ممکن برای کاوش وجود دارد. اما برای 30 شهر بیش از 10 شهر وجود دارد30 مسیرهای ممکن و از آنجا تعداد آنها به طور چشمگیری افزایش می یابد. بزرگترین مشکل در طراحی الگوریتمی است که به سرعت مشکل را در همه موارد حل می کند، برای همه اعداد صحیح N. دانشمندان رایانه بر اساس نظریه پیچیدگی الگوریتمی متقاعد شده اند که چنین الگوریتمی وجود ندارد، بنابراین تأیید می کنند که P ≠ NP .
نمونه های بسیار دیگری از مشکلات غیر قابل حل مانند این وجود دارد. به عنوان مثال، فرض کنید که شما یک جدول بزرگ از اعداد با هزاران سطر و هزاران ستون دارید. آیا می‌توانید از میان همه ترکیب‌های ممکن، ترتیب دقیق 10 ردیف و 10 ستون را پیدا کنید تا 100 ورودی او بالاترین مجموع قابل دستیابی را داشته باشند؟ گامارنیک می‌گوید: «ما آنها را وظایف بهینه‌سازی می‌نامیم، زیرا شما همیشه سعی می‌کنید بزرگترین یا بهترین - بزرگترین مجموع اعداد، بهترین مسیر از طریق شهرها و غیره را پیدا کنید.»
دانشمندان کامپیوتر مدت‌هاست متوجه شده‌اند که شما نمی‌توانید الگوریتم سریعی ایجاد کنید که بتواند به طور موثر مشکلاتی مانند حماسه فروشنده دوره گرد را حل کند. گامارنیک گفت: «چنین چیزی احتمالاً به دلایل کاملاً درک شده غیرممکن است. "اما در زندگی واقعی، طبیعت از نقطه نظر رقیب مشکل ایجاد نمی کند. سعی نمی کند شما را با چالش برانگیزترین و دستچین شده ترین مشکلی که قابل تصور است ناامید کند." در واقع، مردم معمولاً در شرایط تصادفی تر و با تخیل کمتر با مشکلاتی مواجه می شوند و این مشکلاتی است که OGP قصد دارد به آنها رسیدگی کند.
قله ها و دره ها
برای درک اینکه OGP چیست، ممکن است ابتدا ببینیم این ایده چگونه شکل گرفت، آموزنده باشد. از دهه 1970، فیزیکدانان به مطالعه شیشه های دوار، موادی با خواص مایعات و جامدات که دارای رفتار مغناطیسی غیرعادی هستند، پرداخته اند. تحقیقات در مورد عینک های دوار منجر به نظریه ای کلی در مورد سیستم های پیچیده شده است که به مسائلی در فیزیک، ریاضیات، علوم کامپیوتر، علم مواد و سایر زمینه ها مربوط می شود. (این اثر جایزه نوبل فیزیک 2021 را برای جورجیو پاریسی به ارمغان آورد)
یکی از مشکلات آزاردهنده‌ای که فیزیکدانان با آن دست و پنجه نرم می‌کنند، تلاش برای پیش‌بینی حالت‌های انرژی، و به‌ویژه پایین‌ترین پیکربندی‌های انرژی، ساختارهای مختلف شیشه‌های اسپین است. این موقعیت گاهی اوقات از طریق "چشم انداز" از قله های بی شمار کوه جدا شده توسط دره ها، جایی که هدف شناسایی بلندترین قله است، به تصویر کشیده می شود. در این حالت، بالاترین قله در واقع پایین‌ترین حالت انرژی است (اگرچه می‌توان تصویر را برگرداند و به جای آن عمیق‌ترین سوراخ را جستجو کرد). گامارنیک توضیح می‌دهد که این یک مشکل بهینه‌سازی است، که از نظر شکلی شبیه به معضل فروشنده دوره گرد است. سوزن در انبار کاه.
فیزیکدانان نشان داده‌اند که می‌توانید با بریدن کوه‌ها به ارتفاع مشخص و از پیش تعیین‌شده و نادیده گرفتن همه چیز زیر این حد، این تصویر را ساده کنید و به سمت راه‌حل گام بردارید. سپس با مجموعه‌ای از قله‌ها باقی می‌ماند که بالای همان لایه ابرها بیرون زده‌اند، که هر نقطه از این قله‌ها راه‌حلی بالقوه برای مشکل اصلی است.
گامارنیک و همکارانش در مقاله‌ای در سال 2014 متوجه چیزی شدند که قبلاً نادیده گرفته شده بود. در برخی موارد، آنها متوجه می شوند که قطر هر قله بسیار کوچکتر از فاصله بین قله های مختلف خواهد بود. بنابراین، اگر مجبور بودیم هر دو نقطه از این منظره کشیده را انتخاب کنیم - هر دو "راه حل" ممکن - آنها یا بسیار نزدیک (اگر از یک قله می آیند) یا بسیار دور از یکدیگر (اگر از متفاوت استخراج شوند) خواهند بود. قله ها). به عبارت دیگر، در این فواصل یک «شکاف» خائنانه وجود خواهد داشت - چه کوچک و چه بزرگ، اما هیچ چیز در این میان. سیستمی در این حالت که توسط Gamarnik و همکارانش پیشنهاد شده است، با OGP مشخص می شود.
گامارنیک می‌گوید: «ما دریافتیم که همه مسائل شناخته‌شده با ماهیت دلخواه، که از نظر الگوریتمی دشوار هستند، نسخه‌ای از این ویژگی دارند» - یعنی قطر کوه در مدل شماتیک بسیار کوچکتر از فضای بین کوه‌ها است. "این اندازه گیری دقیق تری از سختی الگوریتمی را ارائه می دهد."
اسرار پیچیدگی الگوریتمی را باز کنید
ظهور OGP می تواند به محققان در ارزیابی دشواری ایجاد الگوریتم های سریع برای مقابله با مشکلات خاص کمک کند. و این قبلاً به آنها اجازه داده است که این کار را از نظر ریاضی انجام دهند [and] ما به طور خاص یاد گرفته‌ایم که الگوریتم‌های پایدار - آنهایی که خروجی آنها در صورت تغییر جزئی ورودی تغییر چندانی نمی‌کند - نمی‌توانند این نوع مسائل را حل کنند.» این نتیجه منفی نه تنها برای رایانه‌های معمولی، بلکه برای رایانه‌های کوانتومی نیز صدق می‌کند. و به‌ویژه به اصطلاح «الگوریتم‌های بهینه‌سازی تقریب کوانتومی» (QAOA) که برخی از محققان امیدوار بودند همین مسائل بهینه‌سازی را حل کنند. اکنون، به لطف یافته‌های Gamarnick و همکارانش، این امیدها توسط تشخیص این که برای موفقیت الگوریتم های نوع QAOA به لایه های زیادی از عملیات نیاز است که می تواند یک چالش فنی باشد.
او گفت: "این که این خبر خوب یا بد باشد بستگی به دیدگاه شما دارد." «فکر می‌کنم این خبر خوبی است به این معنا که به ما کمک می‌کند اسرار پیچیدگی الگوریتمی را باز کنیم و دانش خود را در مورد آنچه در قلمرو احتمالات است و آنچه نیست، بهبود می‌بخشد. این خبر بدی است به این معنا که به ما می گوید این مشکلات دشوار هستند، حتی اگر طبیعت آنها را ایجاد کند و حتی اگر به طور تصادفی ایجاد شوند. او افزود: «این خبر تعجب آور نیست.» بسیاری از ما همیشه منتظر آن بوده ایم. اما اکنون ما مبنای قوی تری برای طرح این ادعا داریم."
این امر هنوز محققان را سال‌ها نوری از اثبات عدم وجود الگوریتم‌های سریع که می‌توانند این مسائل بهینه‌سازی را در تنظیمات تصادفی حل کنند، فاصله می‌دهد. وجود چنین شواهدی پاسخ قطعی به مسئله P ≠ NP ارائه می دهد. او می‌گوید: «اگر بتوانیم نشان دهیم که نمی‌توانیم الگوریتمی داشته باشیم که بیشتر اوقات کار می‌کند، این به ما می‌گوید که مطمئناً نمی‌توانیم الگوریتمی داشته باشیم که همیشه کار کند.»
پیش بینی اینکه چقدر طول می کشد تا مسئله P ≠ NP حل شود، به خودی خود یک مشکل غیر قابل حل به نظر می رسد. احتمالاً قله‌های زیادی برای صعود و دره‌هایی برای عبور وجود خواهد داشت تا محققان دید واضح‌تری از وضعیت داشته باشند.
نقل قول: محقق ابزار جدیدی برای درک مسائل محاسباتی سختی که غیرقابل حل به نظر می‌رسند توسعه می‌دهد (۲۰۲۲، ۱۰ ژانویه)، بازیابی شده در ۱۰ ژانویه ۲۰۲۲ از https://phys.org/news/2022-01-tool-hard-problems- intractable.html
این برگه یا سند یا نوشته تحت پوشش قانون کپی رایت است. به جز هرگونه معامله منصفانه به منظور تحقیق یا مطالعه خصوصی، هیچ بخشی بدون اجازه کتبی قابل تکثیر نیست. محتوا فقط برای مقاصد اطلاعاتی ارائه شده است.
[ad_2]