شماره 15 حد مخفی یک شبکه بی نهایت را توصیف می کند

به عنوان دانشجوی کارشناسی در دانشگاه شیلی، برناردو سوبرکاسو به استفاده از رایانه برای انجام ریاضیات نگاه ضعیفی داشت. به نظر می رسید که این با کشف واقعی فکری مخالف باشد.

او گفت: «در مقابل استفاده از رایانه برای حل مشکلاتتان، برخی واکنش‌های غریزی یا غریزی وجود دارد، مانند این که با زیبایی ایده‌آل یا ظرافت یک استدلال فوق‌العاده مخالف است».

اما سپس در سال 2020 سوبرکاسو عاشق شد و همانطور که اغلب اتفاق می افتد، اولویت های او تغییر کرد. موضوع وسواس او سؤالی بود که در یک انجمن آنلاین دید. اکثر مشکلات را اسکن کرد و فراموش کرد، اما این یکی توجه او را جلب کرد. به سمت راست تند زد.

او گفت: "اولین کاری که انجام دادم این بود که پست را در گروه فیس بوک لایک کردم، به این امید که بعداً وقتی کسی راه حلی را پست کرد، یک اعلان دریافت کنم."

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

در آنجا، در آگوست 2021، او یک برخورد تصادفی با مارین هوله، یک دانشمند کامپیوتر که از قدرت محاسباتی عظیم برای حل سوالات سخت ریاضی استفاده می کند. سوبرکاسو از هیوله پرسید که آیا می‌خواهد این مشکل را حل کند، و همکاری‌ای را آغاز کرد که در ژانویه امسال به اوج خود رسید. یک برهان که با یک عدد خلاصه می شود: 15.

هر راه ممکن

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

در نهایت آنها به مشکلی رسیدند که با یک شبکه شروع می شود، مانند یک ورق کاغذ نمودار که برای همیشه ادامه دارد. هدف پر کردن آن با اعداد است. فقط یک محدودیت وجود دارد: فاصله بین هر رخداد یک عدد باید بیشتر از خود عدد باشد. (فاصله با جمع کردن جداسازی عمودی و افقی با هم اندازه‌گیری می‌شود، معیاری که به عنوان فاصله تاکسی شناخته می‌شود، برای نحوه حرکت آن در خیابان‌های شهری شبکه‌ای.) یک جفت 1 نمی‌تواند سلول‌های مجاور را اشغال کند، که فاصله تاکسی‌ها 1 است. اما آنها را می توان در سلول های مورب مستقیم قرار داد که فاصله آنها 2 است.

در ابتدا، گدارد و همکارانش می خواستند بدانند که آیا حتی می توان یک شبکه بی نهایت را با مجموعه ای محدود از اعداد پر کرد یا خیر. اما تا زمانی که او و چهار همکارش این مشکل "رنگ آمیزی بسته بندی" را منتشر کرد در مجله Ars Combinatoria در سال 2008 آنها ثابت کرده بودند که با استفاده از 22 عدد قابل حل است. آنها همچنین می دانستند که هیچ راهی وجود ندارد که فقط با پنج عدد حل شود. این بدان معناست که پاسخ واقعی به مشکل - حداقل تعداد اعداد مورد نیاز - جایی در این بین قرار دارد.

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

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

مشکل، همانطور که بعداً مشخص شد، این است که نشان دادن اینکه شبکه را نمی توان با مجموعه ای از اعداد پوشش داد بسیار دشوارتر از نشان دادن این است که می تواند. گدارد گفت: "این فقط نشان دادن این نیست که یک راه کار نمی کند، بلکه نشان می دهد که هر راه ممکن کار نمی کند."

پس از اینکه سوبرکاسو در CMU شروع به کار کرد و هیول را متقاعد کرد که با او کار کند، آنها به سرعت راهی برای پوشش شبکه با 15 عدد پیدا کردند. آنها همچنین توانستند امکان حل مشکل را تنها با 12 عدد رد کنند. اما احساس پیروزی آنها کوتاه مدت بود، زیرا آنها متوجه شدند که آنها صرفاً نتایجی را که برای مدت طولانی وجود داشت بازتولید می کردند: در سال 2017، محققان می دانستند که پاسخ آنها کمتر از 13 یا بیشتر از 15 نیست. .

برای دانش آموز سال اولی که استاد بزرگی را مجبور کرده بود تا روی مشکل حیوان خانگی خود کار کند، این یک کشف ناراحت کننده بود. "من وحشت کردم. من اساساً چندین ماه بدون اینکه متوجه این موضوع باشم روی یک مشکل کار کرده بودم و حتی بدتر از آن، Marijn را ساخته بودم وقتش را روی آن تلف کند!» سابرکیزو نوشت در یک پست وبلاگ خلاصه کار خود را.

با این حال، هیول کشف نتایج گذشته را نیروبخش یافت. این نشان داد که محققان دیگر مشکل را به اندازه کافی مهم می‌دانستند تا روی آن کار کنند، و برای او تأیید کردند که تنها نتیجه‌ای که ارزش به دست آوردن دارد، حل کامل مشکل است.

او گفت: «وقتی متوجه شدیم که 20 سال روی این مشکل کار شده است، این تصویر کاملاً تغییر کرد.

پرهیز از مبتذل

در طول سال‌ها، هول با یافتن راه‌های کارآمد برای جستجو در میان ترکیب‌های احتمالی بسیار حرفه‌ای دست به کار شده بود. رویکرد او حل SAT نامیده می شود - مخفف "رضایت پذیری". این شامل ساخت یک فرمول طولانی به نام فرمول بولی است که می تواند دو نتیجه ممکن داشته باشد: 0 یا 1. اگر نتیجه 1 باشد، فرمول درست است و مشکل برآورده می شود.

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

متأسفانه، رمزگذاری ساده مسئله رنگ‌آمیزی بسته‌بندی به‌عنوان یک فرمول بولی می‌تواند به میلیون‌ها عبارت کشیده شود - یک رایانه یا حتی ناوگانی از رایانه‌ها می‌توانند برای همیشه تمام روش‌های مختلف تخصیص متغیرها را آزمایش کنند.

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

علاوه بر این، هر بار که یک عدد را به مسئله رنگ آمیزی بسته بندی اضافه می کنید، به دلیل ضرب ترکیب های ممکن، حدود 100 برابر سخت تر می شود. این به این معنی است که اگر یک بانک از رایانه‌هایی که به صورت موازی کار می‌کنند بتوانند 12 را در یک روز محاسبه رد کنند، برای رد کردن 100 به 13 روز زمان محاسباتی نیاز دارند.

هیول و سوبرکاسو افزایش یک رویکرد محاسباتی با نیروی بی رحم را به نوعی مبتذل می دانستند. سابرکاسو گفت: "ما چندین ایده امیدوارکننده داشتیم، بنابراین ما این طرز فکر را در نظر گرفتیم که "بیایید سعی کنیم رویکرد خود را بهینه کنیم تا زمانی که بتوانیم این مشکل را در کمتر از 48 ساعت محاسبه روی خوشه حل کنیم."

برای انجام این کار، آنها باید راه‌هایی برای محدود کردن تعداد ترکیب‌هایی که خوشه محاسباتی باید امتحان می‌کرد، بیابند.

گفت: «[آنها] نه تنها می خواهند آن را حل کنند، بلکه می خواهند آن را به شیوه ای چشمگیر حل کنند الکساندر سویفر از دانشگاه کلرادو، کلرادو اسپرینگز.

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

هیول و سوبرکاسو قوانینی را اضافه کردند که به رایانه اجازه می‌داد ترکیب‌های متقارن را به‌عنوان یکسان در نظر بگیرد و مجموع زمان جستجو را به میزان هشت برابر کاهش داد. آنها همچنین از تکنیکی استفاده کردند که Heule در کارهای قبلی به نام مکعب و تسخیر توسعه داده بود، که به آنها اجازه می داد ترکیب های بیشتری را به موازات یکدیگر آزمایش کنند. اگر می‌دانید که یک سلول معین باید شامل 3، 5 یا 7 باشد، می‌توانید مشکل را تقسیم کنید و هر یک از سه احتمال را به طور همزمان در مجموعه‌های مختلف رایانه آزمایش کنید.

تا ژانویه 2022، این پیشرفت‌ها به هیول و سوبرکاسو اجازه داد تا در آزمایشی که به کمتر از دو روز زمان محاسباتی نیاز داشت، 13 را به عنوان پاسخی برای مشکل رنگ‌آمیزی بسته‌بندی رد کنند. این امر آنها را با دو پاسخ ممکن روبرو کرد: 14 یا 15.

یک پلاس بزرگ

برای رد 14 - و حل مشکل - Heule و Subercaseaux مجبور بودند راه‌های بیشتری برای سرعت بخشیدن به جستجوی رایانه پیدا کنند.

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

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

Heule می‌گوید: «داشتن متغیرهایی که به جای مکان‌های خاص فقط در مورد مثبت‌ها صحبت می‌کنند، بسیار بهتر از صحبت کردن در مورد آنها در سلول‌های خاص بود.

با کمک کارآمدی جستجوی مثبت، هیول و سوبرکاسو در یک آزمایش کامپیوتری در نوامبر 14، 2022 مورد را رد کردند که در نهایت زمان کمتری نسبت به آزمایشی که برای رد کردن 13 استفاده کرده بودند، طول کشید. آنها چهار ماه آینده را صرف تأیید آن کردند. نتیجه‌گیری رایانه درست بود - تقریباً به همان اندازه‌ای که رایانه را در وهله اول برای رسیدن به آن نتیجه صرف کرده بودند.

گودارد گفت: «خوشحال بود که فکر کنیم آنچه که ما به عنوان یک نوع سؤال جانبی در یک مجله تصادفی ایجاد کرده بودیم باعث شده بود گروه‌هایی از مردم ماه‌ها از وقت خود را صرف پیدا کردن چگونگی حل آن کنند. گفت.

برای سوبرکاسو، این اولین پیروزی واقعی در حرفه تحقیقاتی او بود. و در حالی که ممکن است آن نوع کشفی که او برای اولین بار به کار در ریاضیات فکر می کرد، ایده آل نبود، اما دریافت که در نهایت، این کشف پاداش های فکری خود را دارد.

او گفت: "درک فرمی نیست که شما تخته سیاه به من می دهید و من می توانم به شما نشان دهم که چرا 15 است." "اما ما به درک چگونگی عملکرد محدودیت های مشکل دست یافته ایم، چقدر بهتر است که یک عدد 6 در اینجا یا یک عدد 7 در آنجا داشته باشیم. ما درک شهودی زیادی به دست آورده ایم.»