15 নম্বরটি একটি অসীম গ্রিডের গোপন সীমা বর্ণনা করে

চিলি বিশ্ববিদ্যালয়ের একজন স্নাতক হিসাবে, বার্নার্দো সুবারকেসাউক্স গণিত করতে কম্পিউটার ব্যবহার করার একটি ম্লান দৃষ্টিভঙ্গি নিয়েছে। এটা বাস্তব বৌদ্ধিক আবিষ্কারের বিরোধী বলে মনে হয়েছিল।

"আপনার সমস্যা সমাধানের জন্য কম্পিউটার ব্যবহার করার বিরুদ্ধে কিছু প্রবৃত্তি বা অন্ত্রের প্রতিক্রিয়া আছে, যেমন এটি একটি দুর্দান্ত যুক্তির আদর্শ সৌন্দর্য বা কমনীয়তার বিরুদ্ধে যায়," তিনি বলেছিলেন।

কিন্তু তারপরে 2020 সালে Subercaseaux প্রেমে পড়েছিল এবং প্রায়শই ঘটে, তার অগ্রাধিকারগুলি পরিবর্তিত হয়েছিল। তার আবেশের বস্তুটি একটি অনলাইন ফোরামে একটি প্রশ্ন দেখেছিল। বেশিরভাগ সমস্যা তিনি স্ক্যান করে ভুলে গেছেন, কিন্তু এটি তার নজর কেড়েছে। সে ডানদিকে সোয়াইপ করল।

তিনি বলেন, “প্রথম কাজটি আমি করেছিলাম ফেসবুক গ্রুপে পোস্টটি লাইক করা, পরবর্তীতে অন্য কেউ একটি সমাধান পোস্ট করলে বিজ্ঞপ্তি পাওয়ার আশায়”।

প্রশ্নটি সংখ্যার সাথে একটি অসীম গ্রিড পূরণ করার বিষয়ে ছিল। এটা ছিল না, এটা পরিণত, সমস্যা ধরনের এক একটি লার্কের উপর সমাধান. এটি করার জন্য, কার্নেগি মেলন ইউনিভার্সিটির স্নাতক স্কুলের জন্য সুবারকাসক্সকে চিলি ছেড়ে যেতে হয়েছিল।

সেখানে, 2021 সালের আগস্টে, তার সাথে একটি আকস্মিক মুখোমুখি হয়েছিল মারিজান হিউল, একজন কম্পিউটার বিজ্ঞানী যিনি কঠিন গণিত প্রশ্ন সমাধানের জন্য ব্যাপক কম্পিউটিং শক্তি ব্যবহার করেন। Subercaseaux Heule কে জিজ্ঞাসা করেছিল যে তিনি সমস্যাটির চেষ্টা করতে চান কিনা, একটি সহযোগিতা শুরু করে যা এই জানুয়ারিতে শেষ হয়েছিল একটি প্রমাণ যেটিকে একটি একক সংখ্যা দিয়ে সংক্ষেপ করা যেতে পারে: 15।

এভরি পসিবল ওয়ে

2002 সালে ওয়েন গডার্ড ক্লেমসন ইউনিভার্সিটির এবং কিছু সমমনা গণিতবিদরা কম্বিনেটোরিক্সে সমস্যায় ঠুকে তুলছিলেন, কিছু নির্দিষ্ট সীমাবদ্ধতা প্রদত্ত রঙিন মানচিত্র সম্পর্কে ক্ষেত্রের মূল ভিত্তি প্রশ্নে নতুন বাঁক নিয়ে আসার চেষ্টা করেছিলেন।

অবশেষে তারা একটি সমস্যায় অবতরণ করে যা একটি গ্রিড দিয়ে শুরু হয়, যেমন গ্রাফ পেপারের একটি শীট যা চিরতরে চলে। লক্ষ্য সংখ্যা দিয়ে এটি পূরণ করা হয়. শুধু একটি সীমাবদ্ধতা আছে: একই সংখ্যার প্রতিটি ঘটনার মধ্যে দূরত্ব অবশ্যই সংখ্যার চেয়ে বেশি হতে হবে। (দূরত্ব মাপা হয় উল্লম্ব এবং অনুভূমিক বিচ্ছেদ একসাথে যোগ করে, একটি মেট্রিক যা "ট্যাক্সিক্যাব" দূরত্ব হিসাবে পরিচিত যেভাবে এটি গ্রিড করা শহুরে রাস্তায় চলার অনুরূপ।) 1s এর একটি জোড়া সংলগ্ন কক্ষগুলি দখল করতে পারে না, যার একটি ট্যাক্সিক্যাবের দূরত্ব 1, কিন্তু এগুলি সরাসরি তির্যক কোষে স্থাপন করা যেতে পারে, যার দূরত্ব 2।

প্রাথমিকভাবে, গডার্ড এবং তার সহযোগীরা জানতে চেয়েছিলেন যে সংখ্যার একটি সসীম সেট দিয়ে একটি অসীম গ্রিড পূরণ করা সম্ভব কিনা। কিন্তু ততক্ষণে তিনি ও তার চার সহযোগী এই "প্যাকিং কালারিং" সমস্যা প্রকাশ করেছে জার্নালে আরস কম্বিনেটরিয়া 2008 সালে, তারা প্রমাণ করেছিল যে এটি 22 সংখ্যা ব্যবহার করে সমাধান করা যেতে পারে। তারা আরও জানত যে শুধুমাত্র পাঁচটি সংখ্যা দিয়ে এটি সমাধানের কোন উপায় নেই। এর অর্থ হল সমস্যার প্রকৃত উত্তর - ন্যূনতম সংখ্যার প্রয়োজন - এর মধ্যে কোথাও থাকা।

গবেষকরা আসলে একটি অসীম গ্রিড পূরণ করেননি। তাদের করতে হয়নি। পরিবর্তে, গ্রিডের একটি ছোট উপসেট নেওয়াই যথেষ্ট — বলুন একটি 10-বাই-10 বর্গক্ষেত্র — এটিকে সংখ্যা দিয়ে পূরণ করুন, তারপর দেখান যে ভরাট উপসেটের কপিগুলি একে অপরের পাশে রাখা যেতে পারে, যেভাবে আপনি কভার করবেন একটি টালি কপি সঙ্গে মেঝে.

Subercaseaux যখন প্রথম সমস্যাটি জানতে পারে, তখন তিনি কলম এবং কাগজ ব্যবহার করে টাইলস খুঁজতে শুরু করেন। তিনি সংখ্যার গ্রিড স্কেচ করবেন, তাদের ক্রস আউট করবেন, আবার চেষ্টা করুন। তিনি শীঘ্রই সেই পদ্ধতিতে ক্লান্ত হয়ে পড়েন এবং তিনি একজন বন্ধুকে একটি ওয়েব-ভিত্তিক টুল ডিজাইন করতে বলেন যা মাইনসুইপার গেমের সাথে সাদৃশ্যপূর্ণ এবং তাকে দ্রুত সংমিশ্রণ পরীক্ষা করার অনুমতি দেয়। আরও কয়েক সপ্তাহ কাজ করার পরে তিনি নিজেকে বোঝাতে পেরেছিলেন যে আটটি সংখ্যা সহ একটি গ্রিড প্যাক করার কোনও উপায় নেই, তবে তিনি এর চেয়ে বেশি কিছু পেতে পারেননি — টাইলগুলি নিতে পারে এমন অনেকগুলি সম্ভাব্য আকার ছিল এবং অনেকগুলি বিভিন্ন উপায়ে তারা সংখ্যা দিয়ে পূরণ করা যেতে পারে।

সমস্যাটি, যেমনটি পরে স্পষ্ট হয়ে যাবে, তা হল যে গ্রিডকে একটি নির্দিষ্ট সংখ্যা দ্বারা আচ্ছাদিত করা যায় না তা দেখানোর চেয়ে এটি দেখানো অনেক বেশি কঠিন। "এটি শুধু দেখানো নয় যে একটি উপায় কাজ করে না, এটি দেখায় যে প্রতিটি সম্ভাব্য উপায় কাজ করে না," গডার্ড বলেছিলেন।

Subercaseaux CMU তে শুরু করার পরে এবং হিউলকে তার সাথে কাজ করতে রাজি করার পরে, তারা দ্রুত 15 নম্বর দিয়ে গ্রিড কভার করার একটি উপায় খুঁজে পায়। তারা শুধুমাত্র 12 নম্বর দিয়ে সমস্যা সমাধানের সম্ভাবনা উড়িয়ে দিতে সক্ষম হয়েছিল। কিন্তু তাদের বিজয়ের অনুভূতি স্বল্পস্থায়ী ছিল, কারণ তারা বুঝতে পেরেছিল যে তারা কেবল সেই ফলাফলগুলি পুনরুত্পাদন করবে যা প্রায় দীর্ঘকাল ধরে ছিল: 2017 সাল পর্যন্ত, গবেষকরা জানতেন উত্তরটি 13-এর কম বা 15-এর বেশি নয়। .

প্রথম বর্ষের স্নাতক ছাত্রের জন্য যিনি একজন বড়-সময়ের অধ্যাপককে তার পোষা প্রাণীর সমস্যা নিয়ে কাজ করতে বাধ্য করেছিলেন, এটি একটি অস্বস্তিকর আবিষ্কার ছিল। "আমি আতঙ্কিত ছিলাম। আমি মূলত এটি বুঝতে না পেরে একটি সমস্যা নিয়ে বেশ কয়েক মাস ধরে কাজ করছিলাম, এবং আরও খারাপ, আমি মারিজন তৈরি করেছি এটা তার সময় নষ্ট!" Subercaseaux লিখেছেন একটি ব্লগ পোস্ট তাদের কাজ recaping.

হিউল অবশ্য অতীতের ফলাফলের আবিষ্কারকে প্রাণবন্ত বলে মনে করেন। এটি প্রমাণ করেছে যে অন্যান্য গবেষকরা সমস্যাটিকে কাজ করার জন্য যথেষ্ট গুরুত্বপূর্ণ বলে মনে করেছেন এবং তার জন্য নিশ্চিত করেছেন যে একমাত্র ফলাফল প্রাপ্তির যোগ্য ছিল সমস্যাটি সম্পূর্ণরূপে সমাধান করা।

"একবার আমরা বুঝতে পেরেছিলাম যে সমস্যাটির উপর 20 বছর কাজ করা হয়েছে, এটি চিত্রটিকে সম্পূর্ণরূপে বদলে দিয়েছে," তিনি বলেছিলেন।

অসভ্যতা এড়িয়ে চলা

বছরের পর বছর ধরে, হিউল বিশাল সম্ভাব্য সংমিশ্রণগুলির মধ্যে অনুসন্ধান করার কার্যকর উপায় খুঁজে বের করে একটি ক্যারিয়ার তৈরি করেছিল। তার পদ্ধতিকে SAT সমাধান বলা হয় - "সন্তুষ্টির" জন্য সংক্ষিপ্ত। এটি একটি বুলিয়ান সূত্র নামে একটি দীর্ঘ সূত্র তৈরি করতে জড়িত, যার দুটি সম্ভাব্য ফলাফল হতে পারে: 0 বা 1। ফলাফল 1 হলে, সূত্রটি সত্য, এবং সমস্যাটি সন্তুষ্ট।

প্যাকিং কালারিং সমস্যার জন্য, সূত্রের প্রতিটি ভেরিয়েবল একটি প্রদত্ত সংখ্যা দ্বারা একটি প্রদত্ত ঘর দখল করেছে কিনা তা প্রতিনিধিত্ব করতে পারে। একটি কম্পিউটার সূত্রটি সন্তুষ্ট করার জন্য ভেরিয়েবল বরাদ্দ করার উপায়গুলি সন্ধান করে। যদি কম্পিউটার এটি করতে পারে, আপনি জানেন যে আপনি যে শর্তগুলি সেট করেছেন তার অধীনে গ্রিড প্যাক করা সম্ভব।

দুর্ভাগ্যবশত, বুলিয়ান সূত্র হিসাবে প্যাকিং কালারিং সমস্যার একটি সহজবোধ্য এনকোডিং লক্ষ লক্ষ টার্মে প্রসারিত হতে পারে — একটি কম্পিউটার, এমনকি কম্পিউটারের একটি বহর, এটির মধ্যে ভেরিয়েবল বরাদ্দ করার সমস্ত ভিন্ন উপায় পরীক্ষা করে চিরতরে চলতে পারে।

"এই নৃশংস শক্তিটি করার চেষ্টা করতে মহাবিশ্ব শেষ না হওয়া পর্যন্ত সময় লাগবে যদি আপনি এটি নির্বোধভাবে করেন," গডার্ড বলেছিলেন। "সুতরাং আপনার এটিকে এমন কিছুতে নামিয়ে আনার জন্য কিছু দুর্দান্ত সরলীকরণ দরকার যা এমনকি সম্ভব।"

তাছাড়া, যতবার আপনি প্যাকিং কালারিং সমস্যায় একটি সংখ্যা যোগ করেন, সম্ভাব্য সংমিশ্রণগুলি যেভাবে গুণিত হয় তার কারণে এটি প্রায় 100 গুণ কঠিন হয়ে যায়। এর মানে হল যে যদি সমান্তরালভাবে কাজ করা কম্পিউটারগুলির একটি ব্যাঙ্ক গণনার এক দিনে 12টি বাতিল করতে পারে, তাহলে 100টি বাতিল করতে তাদের 13 দিনের গণনা সময় লাগবে।

Heule এবং Subercaseaux একটি পাশবিক শক্তি গণনামূলক পদ্ধতির স্কেলিংকে অশ্লীল হিসাবে বিবেচনা করেছেন, একভাবে। "আমাদের বেশ কিছু প্রতিশ্রুতিশীল ধারনা ছিল, তাই আমরা 'আসুন আমাদের দৃষ্টিভঙ্গি অপ্টিমাইজ করার চেষ্টা করি যতক্ষণ না আমরা ক্লাস্টারে 48 ঘন্টার কম গণনার মধ্যে এই সমস্যাটি সমাধান করতে না পারি,'" সুবারকাসউক্স বলেছেন।

এটি করার জন্য, তাদের কম্পিউটিং ক্লাস্টারের চেষ্টা করতে হয়েছিল এমন সংমিশ্রণের সংখ্যা সীমিত করার উপায় নিয়ে আসতে হয়েছিল।

"[তারা] শুধু এটি সমাধান করতে চায় না, কিন্তু এটি একটি চিত্তাকর্ষক উপায়ে সমাধান করতে চায়," বলেন আলেকজান্ডার সোইফার কলোরাডো বিশ্ববিদ্যালয়ের, কলোরাডো স্প্রিংস।

Heule এবং Subercaseaux স্বীকার করেছেন যে অনেক সংমিশ্রণ মূলত একই। আপনি যদি আটটি ভিন্ন সংখ্যা দিয়ে একটি হীরার আকৃতির টাইল পূরণ করার চেষ্টা করছেন, তবে আপনি যে প্রথম নম্বরটি রেখেছেন সেটি মধ্য বর্গক্ষেত্রের একটি উপরে এবং একটি ডানদিকে, অথবা একটি নীচে এবং একটি বাম দিকের হলে তাতে কিছু যায় আসে না। কেন্দ্র বর্গক্ষেত্র। দুটি প্লেসমেন্ট একে অপরের সাথে প্রতিসাম্যপূর্ণ এবং আপনার পরবর্তী পদক্ষেপকে ঠিক একইভাবে সীমাবদ্ধ করে, তাই তাদের উভয়কে পরীক্ষা করার কোন কারণ নেই।

Heule এবং Subercaseaux নিয়মগুলি যোগ করেছে যা কম্পিউটারকে প্রতিসম সমন্বয়কে সমতুল্য হিসাবে বিবেচনা করার অনুমতি দেয়, মোট অনুসন্ধান সময়কে আটের একটি ফ্যাক্টর দ্বারা হ্রাস করে। তারা কিউব এবং কনক্যুয়ার নামে পূর্ববর্তী কাজে হিউলের তৈরি একটি কৌশলও নিযুক্ত করেছিল, যা তাদের একে অপরের সাথে সমান্তরালভাবে আরও সংমিশ্রণ পরীক্ষা করার অনুমতি দেয়। আপনি যদি জানেন যে একটি প্রদত্ত কোষে 3, 5 বা 7টি থাকতে হবে, তাহলে আপনি সমস্যাটিকে বিভক্ত করতে পারেন এবং কম্পিউটারের বিভিন্ন সেটে একই সাথে তিনটি সম্ভাবনার প্রতিটি পরীক্ষা করতে পারেন।

জানুয়ারী 2022 এর মধ্যে এই উন্নতিগুলি হিউল এবং সুবারকেসাউক্সকে একটি পরীক্ষায় প্যাকিং কালারিং সমস্যার উত্তর হিসাবে 13 টিকে বাতিল করার অনুমতি দেয় যার জন্য দুই দিনের কম কম্পিউটিং সময় প্রয়োজন হয়। এটি তাদের দুটি সম্ভাব্য উত্তর দিয়ে রেখেছিল: 14 বা 15।

একটি বড় প্লাস

14 বাদ দিতে — এবং সমস্যাটি সমাধান করতে — হিউল এবং সাবারকেসাউক্সকে কম্পিউটার অনুসন্ধানের গতি বাড়াতে অতিরিক্ত উপায় খুঁজে বের করতে হয়েছিল।

প্রাথমিকভাবে, তারা একটি বুলিয়ান সূত্র লিখেছিল যা গ্রিডের প্রতিটি পৃথক কোষে ভেরিয়েবল বরাদ্দ করেছিল। কিন্তু 2022 সালের সেপ্টেম্বরে, তারা বুঝতে পেরেছিল যে তাদের সেল-বাই-সেল ভিত্তিতে এগিয়ে যাওয়ার দরকার নেই। পরিবর্তে, তারা আবিষ্কার করেছিল যে প্লাস চিহ্নের আকারে পাঁচটি কোষ নিয়ে গঠিত ছোট অঞ্চলগুলি বিবেচনা করা আরও কার্যকর।

তারা তাদের বুলিয়ান সূত্রটি পুনরায় লিখেছে যাতে বেশ কয়েকটি ভেরিয়েবল প্রশ্নগুলি উপস্থাপন করে যেমন: এই প্লাস-আকৃতির অঞ্চলের মধ্যে কোথাও কি 7 আছে? 7টি অঞ্চলের ঠিক কোথায় হতে পারে তা কম্পিউটারকে সনাক্ত করার প্রয়োজন ছিল না। এটি সেখানে ছিল কিনা তা নির্ধারণ করা দরকার - এমন একটি প্রশ্ন যার উত্তর দেওয়ার জন্য উল্লেখযোগ্যভাবে কম গণনামূলক সংস্থান প্রয়োজন।

"নির্দিষ্ট অবস্থানের পরিবর্তে শুধুমাত্র প্লাস সম্পর্কে কথা বলার ভেরিয়েবলগুলি নির্দিষ্ট কক্ষে সেগুলি সম্পর্কে কথা বলার চেয়ে আরও ভাল বলে প্রমাণিত হয়েছে," হিউল বলেছেন।

প্লাস সার্চের দক্ষতার সাহায্যে, হিউল এবং সাবারকাসওক্স 14 সালের নভেম্বরে একটি কম্পিউটার পরীক্ষায় 2022 টিকে বাতিল করেছিল যেটি তারা যে 13 জনকে বাতিল করতে চেয়েছিল তার চেয়ে কম সময় নিয়েছিল। তারা যাচাই করতে পরের চার মাস ব্যয় করেছিল কম্পিউটারের উপসংহারটি সঠিক ছিল - প্রায় যতটা সময় তারা কম্পিউটারকে প্রথম স্থানে সেই উপসংহারে পৌঁছাতে সক্ষম করতে ব্যয় করেছিল।

"এটা ভাবতে তৃপ্তিদায়ক যে আমরা কিছু র্যান্ডম জার্নালে এক ধরণের পার্শ্ব প্রশ্ন হিসাবে যা তৈরি করেছি তা মানুষের দলকে ব্যয় করতে বাধ্য করেছে, যেমনটি দেখা গেছে, কীভাবে এটি সমাধান করা যায় তা খুঁজে বের করার চেষ্টা করার জন্য তাদের কয়েক মাস সময় কেটেছে," গডার্ড বলেছেন

Subercaseaux এর জন্য, এটি তার গবেষণা কর্মজীবনের প্রথম বাস্তব বিজয় ছিল। এবং যদিও এটি এমন আবিষ্কারের ধরণ নাও হতে পারে যখন তিনি প্রথম গণিতে কাজ করার চিন্তা করেছিলেন, তখন তিনি আবিষ্কার করেছিলেন যে শেষ পর্যন্ত এটির নিজস্ব বুদ্ধিবৃত্তিক পুরষ্কার রয়েছে।

"আপনি আমাকে একটি ব্ল্যাকবোর্ড দিয়েছেন যেখানে এটি ফর্মটি বোঝা যাচ্ছে না এবং আমি আপনাকে দেখাতে পারি কেন এটি 15," তিনি বলেছিলেন। “তবে আমরা বুঝতে পেরেছি যে সমস্যার সীমাবদ্ধতাগুলি কীভাবে কাজ করে, এখানে 6 বা সেখানে 7 থাকলে কতটা ভাল। আমরা অনেক স্বজ্ঞাত বোঝাপড়া অর্জন করেছি।"