مشکلی با صدای آسان اعداد را برای جهان ما بسیار بزرگ به دست می دهد | مجله کوانتا

معمولاً کودکان 5 ساله نمی توانند سؤالات را در مرزهای علوم رایانه درک کنند، اما ممکن است اتفاق بیفتد. به عنوان مثال، فرض کنید یک کودک مهدکودک به نام آلیس دو سیب دارد، اما او پرتقال را ترجیح می دهد. خوشبختانه، همکلاسی‌های او یک سیستم تجارت میوه سالم با نرخ‌های مبادله به شدت اعمال‌شده ایجاد کرده‌اند: مثلاً یک سیب را رها کنید و می‌توانید یک موز تهیه کنید. آیا آلیس می‌تواند با برداشتن و برداشتن موز یا طالبی یک سری معاملات را انجام دهد که او را به میوه مورد علاقه‌اش برساند؟

به اندازه کافی ساده به نظر می رسد. گفت: "شما می توانید به مدرسه ابتدایی بروید و آن را به کودکان بگویید." کریستوف هاس، دانشمند کامپیوتر در دانشگاه آکسفورد. "مردم فکر خواهند کرد، "این باید آسان باشد."

اما مسئله ریاضی زیربنای معضل آلیس - به نام مسئله دستیابی برای سیستم های جمع بردار - به طور شگفت انگیزی ظریف است. در حالی که برخی از موارد را می توان به راحتی حل کرد، دانشمندان کامپیوتر نزدیک به نیم قرن تلاش کردند تا درک جامعی از این مشکل ایجاد کنند. اکنون، در یک سری پیشرفت‌ها در چند سال گذشته، آنها دقیقاً مشخص کرده‌اند که این مشکل چقدر می‌تواند پیچیده شود.

به نظر می رسد که این مشکل کودکانه به طرز پوچ و تقریباً کارتونی پیچیده است - آنقدر پیچیده است که عملاً همه مشکلات دیگر مشکلات محاسباتی معروف به نظر خوب، بچه بازی است. سعی کنید تلاش لازم برای حل این مشکل را کمی محاسبه کنید، و به زودی با اعدادی به قدری بزرگ روبرو خواهید شد که حتی با شمارش ارقام آنها به اعدادی دست پیدا خواهید کرد که هرگز نشنیده اید. چنین اعدادی اغلب مقایساتی را با مقیاس جهان دعوت می کنند، اما حتی آن قیاس ها نیز کوتاهی می کنند. گفت: "این کار عدالت را رعایت نمی کند." گئورگ زتزچه، دانشمند کامپیوتر در موسسه سیستم های نرم افزاری ماکس پلانک در کایزرسلاترن، آلمان. "جهان بسیار کوچک است."

در دسترس؟

مسئله دسترس‌پذیری در اصل خود، در مورد اشیاء ریاضی به نام بردارها است که فهرست‌های مرتبی از اعداد هستند. ورودی‌های این فهرست‌ها مؤلفه‌ها و تعداد مؤلفه‌های یک بردار ابعاد آن نامیده می‌شوند. به عنوان مثال، موجودی میوه آلیس را می توان با یک بردار چهار بعدی توصیف کرد.a, b, c, d), اجزای آن نشان دهنده تعداد سیب، موز، طالبی و پرتقال او در هر زمان معین است.

یک سیستم جمع بردار یا VAS، مجموعه ای از بردارها است که انتقال های احتمالی بین حالت ها را در یک سیستم نشان می دهد. برای آلیس، بردار انتقال (-1، -1، 1، 0) نشان دهنده مبادله یک سیب و یک موز با یک طالبی است. مسئله دسترس‌پذیری VAS می‌پرسد آیا ترکیبی از انتقال‌های مجاز وجود دارد که می‌تواند شما را از یک حالت اولیه خاص به یک حالت هدف خاص ببرد - یا به بیان ریاضی، آیا مجموع بردارهای انتقال وجود دارد که بردار شروع را به بردار هدف تبدیل می‌کند. فقط یک نکته وجود دارد: هیچ مولفه ای از بردار که وضعیت سیستم را توصیف می کند نمی تواند به زیر صفر برسد.

گفت: «این یک محدودیت بسیار طبیعی برای مدلی از واقعیت است وویچک چروینسکی، دانشمند کامپیوتر در دانشگاه ورشو. "شما نمی توانید تعداد سیب منفی داشته باشید."

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

برای پاسخ به این سوال، محققان از دو رویکرد مکمل استفاده می کنند. اول، آن‌ها به دنبال نمونه‌هایی از سیستم‌های جمع بردار بسیار پیچیده می‌گردند که در آن تعیین قابلیت دسترسی به حداقل سطح تلاش نیاز دارد. این حداقل‌ها را «محدوده‌های پایین‌تر» در مورد پیچیدگی مسئله می‌نامند - آنها به محققان می‌گویند: «سخت‌ترین سیستم‌ها برای یک معین n حداقل اینقدر سخت هستند.»

دوم، محققان سعی می‌کنند «محدوده‌های بالایی» را ایجاد کنند - محدودیت‌هایی در مورد سختی دسترسی، حتی در شیطانی‌ترین سیستم‌ها. اینها می گویند: «مختل ترین موارد برای یک معین n حداکثر تا این حد سخت هستند.» برای تعیین دقیق میزان دسترسی در پیچیده‌ترین سیستم‌ها، محققان تلاش می‌کنند تا کران‌های پایین را به بالا و کران‌های بالایی را به پایین فشار دهند تا زمانی که به هم برسند.

چیزهای کابوس

سیستم های جمع بردار سابقه طولانی دارند. از دهه 1960، دانشمندان کامپیوتر از آنها برای مدل‌سازی برنامه‌هایی استفاده کردند که محاسبات را به قطعات کوچک زیادی تقسیم می‌کنند و به طور همزمان روی آن قطعات کار می‌کنند. این نوع "محاسبات همزمان" اکنون در همه جا وجود دارد، اما محققان هنوز به طور کامل پایه های ریاضی آن را درک نکرده اند.

در سال 1976، دانشمند کامپیوتر ریچارد لیپتون اولین گام را برای درک پیچیدگی مشکل دسترسی VAS برداشت. او رویه‌ای را برای ساختن سیستم‌ها ایجاد کرد که در آن سریع‌ترین راه برای تعیین اینکه آیا یک حالت از حالت دیگر قابل دسترسی است یا خیر، ترسیم ترتیبی از انتقال‌ها بین آنهاست. این به او اجازه داد تا از طول کوتاه‌ترین مسیر بین دو حالتی که با دقت انتخاب شده‌اند، به‌عنوان معیار دشواری مشکل دسترسی استفاده کند.

پس لیپتون ثابت او می توانست یک سیستم اندازه بسازد n که در آن کوتاه ترین مسیر بین دو حالت شامل بیش از $latex 2^{2^n}$ انتقال است. این حاکی از یک کران پایین نمایی مضاعف مربوط به تلاش مورد نیاز برای تعیین قابلیت دسترسی در سیستم‌های او بود. این یک کشف شگفت‌انگیز بود - رشد نمایی دو برابر کابوس‌های دانشمندان کامپیوتر است. در واقع، محققان اغلب حتی با رشد نمایی معمولی مخالفت می‌کنند، که در مقایسه با آن کمرنگ است: $لاتکس {2^5}= 32$، اما $لاتکس 2^{2^5}$ بیش از 4 میلیارد است.

اکثر محققان فکر می‌کردند که لیپتون پیچیده‌ترین سیستم‌های جمع بردار ممکن را ساخته است، به این معنی که او کران پایین را تا جایی که می‌توانست بالا برده است. تنها چیزی که از دست می‌رود، در این مورد، یک حد بالایی برای همراهی با آن خواهد بود – یعنی اثباتی مبنی بر اینکه هیچ سیستمی وجود ندارد که در آن تعیین قابلیت دسترسی حتی سخت‌تر باشد. اما هیچ کس نمی دانست چگونه این را ثابت کند. دانشمند کامپیوتر ارنست مایر زمانی که او به او نزدیک شد ثابت در سال 1981، اصولاً همیشه امکان دستیابی در هر سیستم جمع بردار وجود دارد. اما اثبات او هیچ حد کمی را در مورد اینکه مشکل می تواند چقدر سخت باشد، قرار نداد. یک طبقه بود، اما سقفی دیده نمی شد.

لیپتون گفت: «مطمئناً به این موضوع فکر می‌کردم. اما بعد از مدتی تسلیم شدم و تا آنجا که می‌توانستم بگویم هیچ‌کس در طول ۴۰ سال پیشرفتی نداشته است.»

در سال 2015، دانشمندان کامپیوتر ژروم لرو و سیلوین اشمیتز در نهایت تاسیس شد یک کران کمی - آنقدر بالا که محققان تصور کردند این فقط اولین گام است که می‌توان آن را پایین انداخت تا به کران پایین لیپتون برسد.

اما این چیزی نیست که اتفاق افتاده است. در سال 2019، محققان مرز پایین‌تری را به مراتب بالاتر از لیپتون کشف کردند که دهه‌ها عقل متعارف را به هم زد. مشکل دسترسی VAS بسیار پیچیده تر از آن چیزی بود که هر کسی پیش بینی می کرد.

برج قدرت

نتیجه تکان دهنده 2019 ناشی از شکست بود. در سال 2018، چروینسکی یک حدس توسط Leroux و فیلیپ مازوویکی، یک دانشمند کامپیوتر در حال حاضر در دانشگاه ورشو، که می تواند به پیشرفت در یک مشکل مرتبط کمک کند. در بحث‌های بعدی، محققان به یک روش جدید امیدوارکننده برای ساختن سیستم‌های اضافه بردار فوق‌پیچیده دست زدند، که می‌تواند حاکی از یک کران پایینی جدید در مسئله دسترسی VAS باشد، جایی که پیشرفت برای مدت طولانی متوقف شده بود.

چروینسکی به یاد می آورد: "همه چیز در ذهن من به قابلیت دسترسی VAS مرتبط بود." در طول یک ترم با بار آموزشی سبک، او تصمیم گرفت به همراه Leroux، Mazowiecki و دو محقق دیگر به طور انحصاری روی آن مشکل تمرکز کند. اسلاومیر لاسوتا از دانشگاه ورشو و رانکو لازیچ از دانشگاه وارویک.

پس از چند ماه تلاش آنها نتیجه داد. چروینسکی و همکارانش نشان آنها می‌توانند سیستم‌های جمع بردار را بسازند که در آن کوتاه‌ترین مسیر بین دو حالت مربوط به اندازه سیستم باشد، با یک عملیات ریاضی به نام تتراسیون که باعث می‌شود حتی رشد نمایی دوگانه کابوس‌وار رام به نظر برسد.

تتراسیون گسترش مستقیم الگویی است که آشناترین عملیات در ریاضیات را به هم متصل می کند و با جمع شروع می شود. با هم اضافه کنید n کپی از یک عدد، و نتیجه برابر است با ضرب آن عدد در n. اگر با هم ضرب کنید n کپی یک عدد، که معادل توان یا افزایش عدد به nقدرت ام تتراسیون، که اغلب با یک جفت فلش به سمت بالا نشان داده می شود، مرحله بعدی در این دنباله است: تتراسیون یک عدد توسط n به معنای تصدیق آن است n بار برای تولید برج قدرت n داستان های بالا

سخت است که سر خود را در مورد اینکه چقدر سریع تتراشن از کنترل خارج می شود: $latex 2 uparrowuparrow 3$، یا $latex 2^{2^2}$، 16 است، $latex 2 uparrowuparrow 4$ کمی بیش از 65,000 است، و $latex 2 uparrowuparrow 5$ عددی با نزدیک به 20,000 رقم است. نوشتن تمام ارقام $latex 2 uparrowuparrow 6$ از نظر فیزیکی غیرممکن است - یک تعهد زندگی در چنین جهان کوچکی.

چروینسکی و همکارانش در نتیجه مهم خود ثابت کردند که سیستم‌های جمع برداری اندازه وجود دارد n جایی که بهترین راه برای تعیین قابلیت دسترسی، ترسیم مسیری است که شامل بیش از $latex 2 uparrowuparrow n$ انتقال است، که دلالت بر یک کران پایینی جدید دارد که لیپتون را کوتوله کرده است. اما به همان اندازه که تتراسیون سرگردان است، هنوز کلمه نهایی در مورد پیچیدگی مشکل نبود.

به Quinquagintillion و فراتر از آن 

تنها چند ماه پس از کران پایین تکان دهنده جدید در مورد پیچیدگی دسترسی VAS، Leroux و Schmitz رانده شد حد بالایی که آنها سه سال پیش از آن ایجاد کرده بودند، اما تا آخر راه را نرسیدند. در عوض، آنها ثابت کردند که پیچیدگی مسئله دسترسی نمی تواند سریعتر از یک هیولای ریاضی به نام تابع آکرمن رشد کند.

برای درک این تابع، الگوی مورد استفاده برای تعریف تتراسیون را به نتیجه بد آن ببرید. عملیات بعدی در دنباله، به نام پنتاسیون، نشان دهنده تتراسیون مکرر است. به دنبال آن عملیات دیگری (هگزاسیون) برای پنتاسیون مکرر و غیره انجام می شود.

تابع Ackermann که به $latex A(n)$ نشان داده می شود، چیزی است که وقتی یک پله از این نردبان عملیات با هر توقف در خط عددی حرکت می کنید، به دست می آورید: $latex A(1) = 1 + 1$، $latex A. (2) = 2 × 2$، $latex A(3) = 3^3$، $latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$، و غیره. تعداد ارقام در $لاتکس A(4)$ به خودی خود عدد عظیمی است که تقریباً برابر با 1 کوین کواگینتیلیون است - این نام عجیب و غریب و به ندرت مورد نیاز برای یک 1 است که 153 صفر به دنبال آن وجود دارد. توصیه کرد: نگران آکرمن 5 نباشید خاویر اسپارزا، دانشمند کامپیوتر در دانشگاه فنی مونیخ.

نتیجه Leroux و Schmitz یک شکاف بزرگ بین مرزهای پایین و بالایی ایجاد کرد - پیچیدگی دقیق مشکل دسترسی به VAS می‌تواند در هر دو انتهای محدوده یا هر نقطه‌ای از این بین باشد. چروینسکی قصد نداشت اجازه دهد این شکاف باقی بماند. او گفت: "ما به کار روی این کار ادامه دادیم زیرا واضح بود که این بزرگترین کاری است که در زندگی خود انجام داده ایم."

موفقیت نهایی در سال 2021 اتفاق افتاد، در حالی که چروینسکی به یک دانشجوی سال دوم کارشناسی به نام Łukasz Orlikowski مشاوره می داد. او یک نوع ساده از مسئله را به اورلیکوفسکی اختصاص داد تا او را به سرعت برساند، و کار اورلیکوفسکی به آن دو کمک کرد تا تکنیک جدیدی را توسعه دهند که برای مسئله دسترسی عمومی نیز کاربرد داشت. که به آنها اجازه داد کران پایین را بالا ببرید اساساً - تا حد بالایی لرو و اشمیتز آکرمن. با کار مستقل، Leroux به دست آورد یک نتیجه معادل تقریباً در همین زمان

در نهایت، محققان پیچیدگی واقعی مشکل دسترسی را مشخص کردند. کران پایینی Czerwiński، Orlikowski و Leroux نشان دادند که دنباله ای از سیستم های جمع بردار به تدریج بزرگتر وجود دارد که در آن کوتاه ترین مسیر بین دو حالت متناسب با تابع آکرمن رشد می کند. کران بالای لروکس و اشمیتز نشان داد که مشکل دسترسی نمی‌تواند پیچیده‌تر از این باشد - برای هر کسی که امیدوار به یک روش عملی خطاناپذیر برای حل آن است، تسلی کمی دارد. این یک تصویر قابل توجه از این است که مسائل محاسباتی به ظاهر ساده چقدر می توانند ظریف باشند.

هرگز تمام نشد

محققان پس از تعیین پیچیدگی دقیق آن، به مطالعه مشکل دسترسی به VAS ادامه داده اند، زیرا بسیاری از انواع این سوال بی پاسخ مانده اند. برای مثال، کران های بالا و پایین آکرمن، تفاوتی بین روش های مختلف افزایش قائل نمی شوند. n, مانند افزایش ابعاد بردارها یا افزایش تعداد انتقال های مجاز.

اخیراً چروینسکی و همکارانش چنین کرده اند پیشرفت کرد جداسازی این اثرات متمایز با مطالعه سرعت افزایش پیچیدگی در انواع سیستم‌های جمع برداری با ابعاد ثابت. اما هنوز کارهای بیشتری باید انجام شود - حتی در سه بعدی، جایی که سیستم‌های جمع بردار به راحتی قابل تجسم هستند، پیچیدگی دقیق مشکل دسترسی ناشناخته باقی می‌ماند.

Mazowiecki گفت: "به نوعی، این فقط برای ما شرم آور است."

محققان امیدوارند که درک بهتر موارد نسبتاً ساده به آنها کمک کند تا ابزارهای جدیدی را برای مطالعه سایر مدل‌های محاسباتی که پیچیده‌تر از سیستم‌های جمع برداری هستند توسعه دهند. در حال حاضر، ما تقریباً چیزی در مورد این مدل های پیچیده تر نمی دانیم.

Zetzsche گفت: "من این را به عنوان بخشی از یک تلاش بسیار اساسی برای درک قابلیت محاسبه می بینم."

کوانتوم در حال انجام یک سری نظرسنجی برای ارائه خدمات بهتر به مخاطبانمان است. ما را بگیر نظرسنجی خواننده علوم کامپیوتر و شما برای برنده شدن رایگان وارد خواهید شد کوانتوم کالا