গণিতবিদরা 'গোলাকার কিউব' তৈরির জন্য কোয়েস্ট সম্পূর্ণ করেছেন

চতুর্থ শতাব্দীতে, আলেকজান্দ্রিয়ার গ্রীক গণিতবিদ পাপ্পাস মৌমাছিদের তাদের "জ্যামিতিক পূর্বচিন্তার" জন্য প্রশংসা করেছিলেন। তাদের মধুচক্রের ষড়ভুজ কাঠামোটি সমান ক্ষেত্রফল এবং ন্যূনতম ঘেরের কোষগুলিতে দ্বি-মাত্রিক স্থানকে ভাগ করার সর্বোত্তম উপায় বলে মনে হয়েছিল - কীটপতঙ্গগুলি তাদের কতটা মোম তৈরি করতে হবে তা কাটাতে এবং তাদের তৈরি করতে কম সময় এবং শক্তি ব্যয় করতে দেয়। মৌচাক

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

এই "ফোম" সমস্যাটি বিস্তৃত অ্যাপ্লিকেশনে পরিণত হয়েছে - পদার্থবিদদের জন্য যারা সাবানের বুদবুদ (বা ফোম) এর আচরণ অধ্যয়ন করেন এবং রসায়নবিদরা স্ফটিকগুলির গঠন বিশ্লেষণ করেন, গণিতবিদরা গোলক-প্যাকিং ব্যবস্থা অন্বেষণ করেন এবং পরিসংখ্যানবিদরা কার্যকর ডেটা-প্রসেসিং কৌশল বিকাশ করেন। .

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

"আমি এই পিছনে এবং এগিয়ে ভালোবাসি," বলেন আসাফ নাওর প্রিন্সটন বিশ্ববিদ্যালয়ের। “কিছু পুরানো গণিত কম্পিউটার বিজ্ঞানের সাথে প্রাসঙ্গিক হয়ে ওঠে; কম্পিউটার বিজ্ঞান অর্থ প্রদান করে এবং গণিতে প্রশ্ন সমাধান করে। এটা যখন ঘটে তখন খুব ভালো লাগে।”

কিন্তু সেই আকৃতি, যদিও সর্বোত্তম, গুরুত্বপূর্ণ কিছু অনুপস্থিত ছিল: একটি জ্যামিতিক ভিত্তি। কম্পিউটার বিজ্ঞানের কৌশল ব্যবহার করে এর অস্তিত্ব প্রমাণিত হওয়ায় এর প্রকৃত জ্যামিতি বোঝা কঠিন ছিল। সেটাই নাওর, সাথে ওডেড রেগেভ, নিউ ইয়র্ক ইউনিভার্সিটির কৌরান্ট ইনস্টিটিউটের একজন কম্পিউটার বিজ্ঞানী, সংশোধন করতে রওনা হন গত মাসে অনলাইনে পোস্ট করা একটি প্রমাণ.

"এটি গল্পের একটি খুব সুন্দর সমাপ্তি," রেগেভ বলেছেন।

কিউবিকাল ফোম

গণিতবিদরা ফোমের সমস্যার অন্যান্য সংস্করণগুলি বিবেচনা করেছেন — আপনি যদি পূর্ণসংখ্যা জালি বলা হয় সেই অনুযায়ী শুধুমাত্র পার্টিশন স্পেস দেওয়ার অনুমতি দেওয়া হয় তবে কী হবে তা সহ। সমস্যার সেই সংস্করণে, আপনি সমানভাবে ব্যবধানযুক্ত বিন্দুগুলির একটি বর্গাকার অ্যারে নিন (প্রতিটি 1 ইউনিট আলাদা) এবং সেই বিন্দুগুলির প্রতিটিকে একটি আকৃতির কেন্দ্রে পরিণত করুন। "কিউবিকাল" ফোমের সমস্যাটি জিজ্ঞাসা করে যে আপনি যখন এইভাবে টাইল স্পেস দিতে হবে তখন সর্বনিম্ন পৃষ্ঠের ক্ষেত্রফল কী হবে।

গবেষকরা প্রাথমিকভাবে ম্যানিফোল্ড নামক টপোলজিক্যাল স্পেসের বৈশিষ্ট্য বোঝার জন্য এই সীমাবদ্ধতা আরোপ করতে আগ্রহী ছিলেন। কিন্তু প্রশ্নটি তার নিজস্ব জীবন নিয়েছিল, ডেটা বিশ্লেষণ এবং অন্যান্য অ্যাপ্লিকেশনগুলিতে প্রাসঙ্গিক হয়ে উঠেছে।

এটি জ্যামিতিকভাবেও আকর্ষণীয়, কারণ এটি "অনুকূল" বলতে যা বোঝায় তা পরিবর্তন করে। দুটি মাত্রায়, উদাহরণস্বরূপ, নিয়মিত ষড়ভুজগুলি আর সমতলকে টাইল করতে পারে না যদি সেগুলিকে শুধুমাত্র অনুভূমিক এবং উল্লম্ব দিকগুলিতে পূর্ণসংখ্যার পরিমাণ দ্বারা স্থানান্তরিত করা যায়। (আপনাকে দুটি দিকের একটিতে অযৌক্তিক পরিমাণে তাদের সরাতে হবে।)

বর্গক্ষেত্র পারে. কিন্তু যে সেরা যে করা যেতে পারে? গণিতবিদ হিসেবে জাইগইয়ং চো 1989 সালে আবিষ্কৃত, উত্তর হল না। সর্বোত্তম আকৃতিটি পরিবর্তে একটি ষড়ভুজ যা এক দিকে স্কোয়াশ করা হয়েছে এবং অন্য দিকে লম্বা করা হয়েছে। (এই ধরনের একটি ষড়ভুজের পরিধি প্রায় 3.86 হয় যখন এর ক্ষেত্রফল 1 হয় - 4-এর বর্গক্ষেত্রের পরিধিকে ছাড়িয়ে যায়।)

এই পার্থক্যগুলি তুচ্ছ মনে হতে পারে, কিন্তু উচ্চ মাত্রায় তারা অনেক বড় হয়।

একটি প্রদত্ত আয়তনের সমস্ত আকারের মধ্যে, যেটি পৃষ্ঠের ক্ষেত্রফলকে ছোট করে তা হল গোলক। হিসাবে n, মাত্রার সংখ্যা, বৃদ্ধি পায়, গোলকের পৃষ্ঠের ক্ষেত্রফল বর্গমূলের অনুপাতে বৃদ্ধি পায় n.

কিন্তু গোলক ফাঁক না রেখে একটি স্থান টাইল করতে পারে না। অন্যদিকে, একটি nআয়তন 1 এর মাত্রিক ঘনক ক্যান। ধরা হল যে এর পৃষ্ঠের ক্ষেত্রফল 2n, তার মাত্রা সরাসরি অনুপাতে ক্রমবর্ধমান. আয়তন 10,000-এর একটি 1-মাত্রিক ঘনক্ষেত্রের 20,000 পৃষ্ঠের ক্ষেত্রফল রয়েছে - 400-এর চেয়ে অনেক বড়, একটি 10,000-মাত্রিক গোলকের আনুমানিক পৃষ্ঠের ক্ষেত্রফল।

এবং তাই গবেষকরা ভেবেছিলেন যে তারা একটি "গোলাকার ঘনক" খুঁজে পেতে পারে - এমন একটি আকৃতি যা টাইল করে n-মাত্রিক স্থান, একটি ঘনকের মতো, কিন্তু যার পৃষ্ঠের ক্ষেত্রফল একটি গোলকের মতো ধীরে ধীরে বৃদ্ধি পায়।

এটা অসম্ভাব্য মনে হয়েছিল. "আপনি যদি চান যে আপনার বুদবুদটি সঠিকভাবে স্থান পূরণ করতে এবং এই ঘনক গ্রিডে কেন্দ্রীভূত হতে, তাহলে একটি ঘনক বুদবুদ ছাড়া আপনি কী ব্যবহার করবেন সে সম্পর্কে চিন্তা করা কঠিন," বলেন রায়ান ও'ডোনেল, কার্নেগি মেলন বিশ্ববিদ্যালয়ের একজন তাত্ত্বিক কম্পিউটার বিজ্ঞানী। "এটি সত্যিই মনে হচ্ছে ঘনক্ষেত্রটি সেরা হওয়া উচিত।"

আমরা এখন জানি যে এটা না.

কঠিন সমস্যার কঠোরতা

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

দ্বারা 2002 সালে প্রস্তাবিত সুভাষ খোট, সেই সময়ে একজন স্নাতক ছাত্র, অনুমানটি পোষণ করে যে যদি একটি নির্দিষ্ট সমস্যা - যা একটি নেটওয়ার্কের নোডগুলিতে রঙ নির্ধারণের সাথে জড়িত - ঠিকভাবে সমাধান করা যায় না, তাহলে এমনকি একটি আনুমানিক সমাধান খুঁজে পাওয়া খুব কঠিন। যদি সত্য হয়, অনুমানটি গবেষকদেরকে এক ধাক্কায় অন্যান্য গণনামূলক কাজের একটি বিশাল ভাণ্ডারের জটিলতা বোঝার অনুমতি দেবে।

কম্পিউটার বিজ্ঞানীরা প্রায়শই কাজগুলিকে একটি দক্ষ অ্যালগরিদম দিয়ে সমাধান করা যায় কিনা বা সেগুলি "NP-হার্ড" (অর্থাৎ সমস্যার আকার বাড়ার সাথে সাথে দক্ষতার সাথে সমাধান করা যায় না, যতক্ষণ না ব্যাপকভাবে বিশ্বাস করা হয়) তার উপর ভিত্তি করে শ্রেণীবদ্ধ করে। কিন্তু গণনাগত জটিলতা সম্পর্কে অপ্রমাণিত অনুমান সত্য)। উদাহরণস্বরূপ, ভ্রমণ বিক্রয়কর্মী সমস্যা, যা একটি নেটওয়ার্কের প্রতিটি শহরে শুধুমাত্র একবার পরিদর্শন করার জন্য প্রয়োজনীয় সংক্ষিপ্ত পথের জন্য জিজ্ঞাসা করে, NP-হার্ড। তাই নির্ধারণ করা হচ্ছে একটি গ্রাফ - প্রান্ত দ্বারা সংযুক্ত শীর্ষবিন্দুর একটি সংগ্রহ - সর্বাধিক তিনটি রঙের সাথে লেবেল করা যেতে পারে যাতে যেকোনো দুটি সংযুক্ত শীর্ষবিন্দুর ভিন্ন রঙ থাকে।

দেখা যাচ্ছে যে এই কাজগুলির অনেকগুলির জন্য এমনকি একটি আনুমানিক সমাধান খুঁজে পাওয়া NP- কঠিন। বলুন আপনি একটি গ্রাফের শীর্ষবিন্দুকে বিভিন্ন রঙের সাথে লেবেল করতে চান এমনভাবে যা কিছু সীমাবদ্ধতার তালিকাকে সন্তুষ্ট করে। যদি এই সমস্ত সীমাবদ্ধতাগুলি পূরণ করা NP-কঠিন হয়, তবে তাদের মাত্র 90%, বা 75%, বা 50% পূরণ করার চেষ্টা করার বিষয়ে কী হবে? কিছু থ্রেশহোল্ডের নীচে, একটি দক্ষ অ্যালগরিদম নিয়ে আসা সম্ভব হতে পারে, কিন্তু সেই থ্রেশহোল্ডের উপরে, সমস্যাটি NP-হার্ড হয়ে ওঠে।

কয়েক দশক ধরে, কম্পিউটার বিজ্ঞানীরা আগ্রহের বিভিন্ন অপ্টিমাইজেশান সমস্যার জন্য থ্রেশহোল্ডগুলিকে পেরেক দিয়ে কাজ করেছেন। কিন্তু কিছু প্রশ্ন এই ধরনের বর্ণনা এড়িয়ে যায়। যদিও একটি অ্যালগরিদম সর্বোত্তম সমাধানের 80% গ্যারান্টি দিতে পারে, 95% সর্বোত্তম সমাধান অর্জন করা NP-কঠিন হতে পারে, NP-হার্ড অঞ্চলে ঠিক 80% এবং 95% এর মধ্যে সমস্যা টিপস কোথায় এই প্রশ্নটি অমীমাংসিত রেখে।

অনন্য গেম অনুমান, বা UGC, উত্তরটি অবিলম্বে চিহ্নিত করার একটি উপায় সরবরাহ করে। এটি একটি বিবৃতি দেয় যা প্রথমে আরও সীমিত বলে মনে হয়: যে একটি গ্রাফের মধ্যে পার্থক্য বলা NP-কঠিন যার জন্য আপনি একটি নির্দিষ্ট সেট রঙের সীমাবদ্ধতার প্রায় সমস্ত সেট (বলুন, 99% এর বেশি) এবং একটি গ্রাফ যা আপনি সবেমাত্র কোনটিই সন্তুষ্ট করতে পারেন (বলুন, 1% এর কম)।

কিন্তু 2002 সালে UGC প্রস্তাবিত হওয়ার পরপরই, গবেষকরা দেখিয়েছেন যে যদি অনুমানটি সত্য হয়, তাহলে আপনি সহজেই যেকোনো সীমাবদ্ধতা সন্তুষ্টির সমস্যার জন্য কঠোরতা থ্রেশহোল্ড গণনা করতে পারেন। (এর কারণ হল UGC এও বোঝায় যে একটি পরিচিত অ্যালগরিদম এই সমস্ত সমস্যার জন্য সম্ভাব্য সর্বোত্তম আনুমানিকতা অর্জন করে।) "এটি এই সমস্ত অপ্টিমাইজেশন সমস্যার জন্য সঠিকভাবে লিঞ্চপিন ছিল," ও'ডোনেল বলেছিলেন।

এবং তাই তাত্ত্বিক কম্পিউটার বিজ্ঞানীরা UGC প্রমাণ করার জন্য যাত্রা শুরু করেছিলেন - একটি কাজ যা শেষ পর্যন্ত তাদের কয়েকজনকে গোলাকার কিউব আবিষ্কার করতে পরিচালিত করেছিল।

কঠিন সমস্যা কঠিন করা

2005 সালে, ও'ডোনেল মাইক্রোসফ্ট রিসার্চে কাজ করছিলেন। তিনি এবং দুই সহকর্মী- উরিয়েল ফেইজ, এখন উইজম্যান ইনস্টিটিউট অফ সায়েন্সে, এবং গাই কিন্ডলার, এখন জেরুজালেমের হিব্রু ইউনিভার্সিটিতে — ইউজিসি মোকাবেলা করার জন্য দলবদ্ধ হয়েছে৷

তারা কীভাবে এগিয়ে যেতে চায় সে সম্পর্কে তাদের একটি অস্পষ্ট ধারণা ছিল। তারা গ্রাফ সম্পর্কে একটি প্রশ্ন দিয়ে শুরু করবে — যেটি UGC-এর সাথে খুব মিল। তথাকথিত সর্বাধিক কাট ("ম্যাক্স-কাট") সমস্যাটি জিজ্ঞাসা করে, একটি গ্রাফ দেওয়া হলে, কীভাবে এর শীর্ষবিন্দুকে দুটি সেটে (বা রঙে) বিভাজন করা যায় যাতে সেই সেটগুলির সাথে সংযোগকারী প্রান্তের সংখ্যা যতটা সম্ভব বড় হয়। (দুটি রঙের একটি গ্রাফকে রঙ করার সর্বোত্তম উপায় সম্পর্কে প্রশ্ন হিসাবে আপনি সর্বাধিক কাটের কথা ভাবতে পারেন, যাতে যতটা সম্ভব কম প্রান্ত একই রঙের শীর্ষবিন্দুগুলিকে সংযুক্ত করতে পারে।)

যদি UGC সত্য হয়, তাহলে এটি বোঝাবে যে, কিছু র্যান্ডম গ্রাফ দেওয়া হলে, একটি দক্ষ আনুমানিক অ্যালগরিদম সেই গ্রাফের প্রকৃত সর্বোচ্চ কাটার প্রায় 87% এর মধ্যে পেতে পারে। কোন ভাল কাজ করা NP-হার্ড হবে.

Feige, Kindler এবং O'Donnell পরিবর্তে বিপরীত দিকে যেতে চেয়েছিলেন: তারা দেখাতে আশা করেছিল যে সর্বাধিক কাট আনুমানিক করা কঠিন, এবং তারপর UGC প্রমাণ করতে এটি ব্যবহার করুন। তাদের পরিকল্পনা সমান্তরাল পুনরাবৃত্তি নামক একটি কৌশলের শক্তির উপর নির্ভর করে - একটি চতুর কৌশল যা কঠিন সমস্যাগুলিকে কঠিন করে তোলে।

বলুন আপনি জানেন যে আপনি সমাধান করতে পারেন এমন একটি সমস্যা এবং আপনি বেশিরভাগই সমাধান করতে পারেন এর মধ্যে পার্থক্য করা NP- কঠিন। সমান্তরাল পুনরাবৃত্তি আপনাকে আরও শক্তিশালী কঠোরতার ফলাফল দেখানোর জন্য এটি তৈরি করতে সক্ষম করে: যে সমস্যাটি আপনি সমাধান করতে পারেন এবং যেটি আপনি খুব কমই সমাধান করতে পারেন তার মধ্যে পার্থক্য করাও NP- কঠিন। "এই অজ্ঞাত, গভীর ঘটনাটি … আজ অনেক কম্পিউটার বিজ্ঞানের সাহসে রয়েছে," নাওর বলেন।

কিন্তু একটা ক্যাচ আছে। সমান্তরাল পুনরাবৃত্তি সবসময় সমস্যাটির কঠোরতাকে ততটা বাড়িয়ে তোলে না যতটা কম্পিউটার বিজ্ঞানীরা চান। বিশেষ করে, ম্যাক্স-কাট সমস্যার এমন দিক রয়েছে যা "সমান্তরাল পুনরাবৃত্তির জন্য একটি বড় মাথাব্যথা তৈরি করে," রেগেভ বলেছিলেন।

Feige, Kindler এবং O'Donnell মাথাব্যথা সত্ত্বেও সমান্তরাল পুনরাবৃত্তি কাজ করতে পারে দেখানোর উপর দৃষ্টি নিবদ্ধ করেন। "এটি বিশ্লেষণ করার জন্য একটি সত্যিই জটিল জিনিস," বলেন ডানা মোশকোভিটজ, অস্টিনের টেক্সাস বিশ্ববিদ্যালয়ের একজন তাত্ত্বিক কম্পিউটার বিজ্ঞানী। “কিন্তু এইটা খুব কাছের মনে হচ্ছিল। সমান্তরাল পুনরাবৃত্তি দেখে মনে হচ্ছে এটি সর্বাধিক কাট থেকে অনন্য গেমগুলিতে এই সংযোগটিকে [সাহায্য করতে] করবে।"

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

সমান্তরাল পুনরাবৃত্তি আপনাকে এই সমস্যার একটি উচ্চ-মাত্রিক সংস্করণ বিবেচনা করার অনুমতি দেয় — যেটিতে আপনাকে প্রদর্শিত সমস্ত বিজোড় চক্রগুলি ভেঙে ফেলতে হবে। Feige, Kindler এবং O'Donnell কে দেখাতে হবে যে মাত্রার সংখ্যা অনেক বড় হওয়ার সাথে সাথে সমস্ত বিজোড় চক্র ভাঙতে আপনাকে প্রান্তের একটি খুব বড় ভগ্নাংশ মুছে ফেলতে হবে। যদি এটি সত্য হয়, তাহলে এর অর্থ সমান্তরাল পুনরাবৃত্তি কার্যকরভাবে এই "মূর্খ সর্বোচ্চ-কাট" সমস্যার কঠোরতাকে বাড়িয়ে তুলতে পারে।

তখনই দলটি একটি কৌতূহলী কাকতালীয় ঘটনা আবিষ্কার করে: সমান্তরাল পুনরাবৃত্তি তারা যেভাবে আশা করেছিল সেভাবে কাজ করবে কিনা তা ব্যাখ্যা করার একটি জ্যামিতিক উপায় ছিল। গোপন কিউবিকাল ফেনা পৃষ্ঠ এলাকায় পাড়া.

লেবু থেকে লেমনেড পর্যন্ত

তাদের সমস্যা, ফোমের ভাষায় পুনঃলিখিত, গোলাকার কিউব বিদ্যমান থাকতে পারে না তা দেখানোর জন্য ফুটিয়ে তোলা হয়েছে - যে পূর্ণসংখ্যা জালি বরাবর উচ্চ-মাত্রিক স্থানকে ঘনক্ষেত্রের তুলনায় অনেক ছোট পৃষ্ঠের ক্ষেত্রফলের কোষগুলিতে ভাগ করা অসম্ভব। (একটি বৃহত্তর পৃষ্ঠ এলাকা বিজোড়-চক্র গ্রাফে আরও "খারাপ" প্রান্ত মুছে ফেলার প্রয়োজনের সাথে মিলে যায়, যেমন কম্পিউটার বিজ্ঞানীরা দেখানোর আশা করেছিলেন।)

"আমরা ছিলাম, ওহ, কী অদ্ভুত জ্যামিতি সমস্যা, কিন্তু এটি সম্ভবত সত্য, তাই না?" ও'ডোনেল বলেছেন। "আমাদের সত্যিকারের উত্তর হওয়ার জন্য এটির প্রয়োজন ছিল।" কিন্তু তিনি, ফেইজ এবং কিন্ডলার তা প্রমাণ করতে পারেননি। তাই 2007 সালে, তারা একটি কাগজ প্রকাশিত UGC-কে আক্রমণ করতে সাহায্য করার জন্য তারা কীভাবে এই সমস্যাটি ব্যবহার করার পরিকল্পনা করেছিল তার রূপরেখা।

শীঘ্রই, তাদের আশা ধূলিসাৎ হয়ে গেল।

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

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

"অদ্বিতীয় গেমগুলির কঠোরতা দেখানোর জন্য সমান্তরাল পুনরাবৃত্তি ব্যবহার করার আমাদের পরিকল্পনা সহজ ক্ষেত্রেও কাজ করেনি," ও'ডোনেল বলেছেন। "এই ধরনের পুরো পরিকল্পনা ভেঙ্গে দিয়েছে।"

যদিও হতাশাজনক, রাজের ফলাফল গোলাকার ঘনক্ষেত্রের অস্তিত্বের ইঙ্গিত দেয়: আকারগুলি টাইলিং করতে সক্ষম n-এর বর্গমূলের অনুপাতে স্কেল করা একটি পৃষ্ঠের ক্ষেত্রফল সহ মাত্রিক স্থান n. ও'ডোনেল বলেন, "আমরা এমনই ছিলাম, ঠিক আছে, আসুন লেবু থেকে লেবুপান তৈরি করি এবং সমান্তরাল পুনরাবৃত্তি এবং বিচ্ছিন্ন গ্রাফ সম্পর্কে এই হতাশাজনক প্রযুক্তিগত ফলাফলটি গ্রহণ করি এবং এটিকে জ্যামিতিতে একটি ঝরঝরে, আকর্ষণীয় ফলাফলে পরিণত করি," ও'ডোনেল বলেছিলেন।

তিনি এবং কিন্ডলার, কম্পিউটার বিজ্ঞানীদের সহযোগিতায় অনুপ রাও এবং আভি উইগডারসন, রাজের প্রমাণের উপর ছিদ্র করা হয়েছে যতক্ষণ না তারা এর কৌশলগুলি ফেনা সমস্যায় অনুবাদ করার জন্য যথেষ্ট ভালভাবে শিখেছে। 2008 সালে, তারা তা দেখিয়েছিল গোলাকার কিউব সত্যিই সম্ভব.

"এটি সমস্যা সম্পর্কে যুক্তি একটি চমৎকার উপায়," বলেন মার্ক ব্র্যাভারম্যান প্রিন্সটনের। "ইহা সুন্দর."

এবং এটি গল্পের জ্যামিতি দিকে প্রশ্ন উত্থাপন করেছে। কারণ তারা তাদের টাইলিং আকৃতি নির্মাণের জন্য সমান্তরাল পুনরাবৃত্তিতে রাজের কাজ ব্যবহার করেছিল, কিন্ডলার, ও'ডোনেল, রাও এবং উইগডারসন কুৎসিত এবং ফ্রাঙ্কেনস্টাইনের মতো কিছু দিয়ে শেষ করেছিলেন। টালি ছিল অগোছালো এবং ইন্ডেন্টেশনে পূর্ণ। গাণিতিক ভাষায়, এটি উত্তল ছিল না। যদিও এটি তাদের উদ্দেশ্যের জন্য কাজ করেছিল, গোলাকার ঘনক্ষেত্রে এমন বৈশিষ্ট্যের অভাব ছিল যা গণিতবিদরা পছন্দ করেন - এমন বৈশিষ্ট্য যা একটি আকৃতিকে আরও কংক্রিট করে, সংজ্ঞায়িত করা এবং অধ্যয়ন করা সহজ এবং সম্ভাব্য অ্যাপ্লিকেশনের জন্য আরও উপযুক্ত।

"তাদের নির্মাণ সম্পর্কে খুব অসন্তুষ্ট কিছু আছে," রেগেভ বলেন. "এটি একটি অ্যামিবার মত দেখাচ্ছে। আপনি যা আশা করবেন তা তেমন দেখাচ্ছে না, একটি সুন্দর টাইলিং বডি।"

সেটাই সে আর নাওর খুঁজে বের করল।

ব্রেকিং ফ্রি অফ দ্য কেজ

শুরু থেকেই, নাওর এবং রেগেভ বুঝতে পেরেছিলেন যে তাদের প্রথম থেকেই শুরু করতে হবে। "আংশিকভাবে কারণ উত্তল দেহগুলি এত সীমাবদ্ধ, পূর্ববর্তী কৌশলগুলির কোনও কাজ করার সুযোগ ছিল না," বলেছেন ডর মিনজার, ম্যাসাচুসেটস ইনস্টিটিউট অফ টেকনোলজির একজন তাত্ত্বিক কম্পিউটার বিজ্ঞানী।

প্রকৃতপক্ষে, এটি সম্পূর্ণরূপে বিশ্বাসযোগ্য ছিল যে উত্তলতা খুব সীমাবদ্ধ হবে - যে একটি উত্তল গোলাকার ঘনক কেবল বিদ্যমান নয়।

কিন্তু গত মাসে, নাওর এবং রেগেভ প্রমাণ করেছেন যে আপনি দেশভাগ করতে পারেন n- পূর্ণসংখ্যা বরাবর মাত্রিক স্থান একটি উত্তল আকৃতির সাথে সমন্বয় করে যার পৃষ্ঠের ক্ষেত্রফল গোলকের কাছাকাছি। এবং তারা এটি সম্পূর্ণরূপে জ্যামিতিকভাবে করেছে — সমস্যাটিকে তার গাণিতিক মূলে ফিরিয়ে দিয়েছে।

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

দ্বি-মাত্রিক গ্রিডের একটি বিন্দু বিবেচনা করুন। এটি অনুভূমিক এবং উল্লম্ব দিকগুলির নিকটতম পয়েন্ট থেকে 1 ইউনিট দূরে অবস্থিত৷ কিন্তু তির্যক দিকে, নিকটতম বিন্দু হল $latex sqrt{2}$ একক দূরে — একটি অসঙ্গতি যা বড় জায়গায় আরও খারাপ হয়। মধ্যে n-মাত্রিক পূর্ণসংখ্যা জালি, নিকটতম বিন্দুগুলি এখনও 1 ইউনিট দূরে, কিন্তু সেই "তির্যক" বিন্দুগুলি এখন $latex sqrt{n}$ ইউনিট দূরে। বলুন, 10,000 মাত্রায়, এর মানে হল যে কোনও বিন্দুর নিকটতম "তির্যক" প্রতিবেশীটি 100 একক দূরে, যদিও সেখানে 10,000টি অন্যান্য বিন্দু (প্রতিটি দিক থেকে একটি) রয়েছে যা শুধুমাত্র 1 ইউনিট দূরে।

অন্যান্য জালিতে, এই দুটি ধরণের দূরত্ব একে অপরের অনুপাতে বৃদ্ধি পায়। গণিতবিদরা কয়েক দশক ধরে জানেন যে কীভাবে ন্যূনতম পৃষ্ঠের ক্ষেত্রফলের উত্তল আকারের সাথে এই জাতীয় জালিগুলিকে টাইল করা যায়।

কিন্তু পূর্ণসংখ্যা জালিতে, সংক্ষিপ্ততম দূরত্ব সর্বদা 1 এ আটকে থাকবে। এটি সর্বোত্তম পৃষ্ঠের ক্ষেত্রফলের একটি সুন্দর-সুদর্শন টাইল নির্মাণের পথে পায়। "তারা আপনাকে এই খাঁচায় ফেলেছে," রেগেভ বলল। "তারা আপনার চারপাশে সবকিছু খুব শক্ত করে তোলে।"

তাই নাওর এবং রেগেভ পরিবর্তে পূর্ণের একটি স্লাইস বিবেচনা করেছেন n-মাত্রিক স্থান। তারা সাবধানে এই সাবস্পেসটি বেছে নিয়েছিল যাতে এটি এখনও পূর্ণসংখ্যা বিন্দুতে সমৃদ্ধ হবে, কিন্তু এই বিন্দুগুলির কোনটিই একসাথে খুব কাছাকাছি হবে না।

অন্য কথায়, তারা যে সাবস্পেস দিয়ে শেষ করেছিল তা ছিল ঠিক সেই ধরনের যে গণিতবিদরা আগে থেকেই জানতেন কিভাবে সর্বোত্তমভাবে টাইল করতে হয়।

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

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

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

"যখন জিনিসগুলি ভিন্নভাবে করা হয়," রাজ যোগ করেছেন, "কখনও কখনও আপনি আকর্ষণীয় অতিরিক্ত প্রভাব খুঁজে পান।"

আশা পুনরুজ্জীবিত

এই প্রভাবগুলি কী হতে পারে তা এখনও স্পষ্ট নয় — যদিও কাজটি ক্রিপ্টোগ্রাফি এবং অন্যান্য অ্যাপ্লিকেশনগুলিতে পূর্ণসংখ্যা জালির সম্ভাব্য ব্যবহারে ট্যাপ করে। এই সমস্যাটি অন্যান্য ক্ষেত্রের সাথে কতটা সংযুক্ত তা বিবেচনা করে, "এটি অন্যান্য জিনিসের দিকে নিয়ে যেতে পারে," অ্যালন বলেছিলেন।

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

Braverman এবং Minzer যখন তারা এই ধরনের একটি উপায় চেষ্টা করেছিল 2020 সালে ফেনা পুনর্বিবেচনা করা হয়েছে. টাইলিং আকৃতি উত্তল হওয়ার প্রয়োজনের পরিবর্তে, তারা বলেছিল যে এটি নির্দিষ্ট প্রতিসাম্যতা মেনে চলে, যাতে আপনি যেভাবেই এর স্থানাঙ্কগুলি উল্টান না কেন এটি একই রকম দেখায়। (2D তে, একটি বর্গক্ষেত্র কাজ করবে, কিন্তু একটি আয়তক্ষেত্র কাজ করবে না; আজ পর্যন্ত বর্ণিত উচ্চ-মাত্রিক গোলাকার কিউবও হবে না।) এই নতুন সীমাবদ্ধতার অধীনে, এই জুটি 15 বছর আগে কিন্ডলার এবং অন্যরা কী আশা করেছিল তা দেখাতে সক্ষম হয়েছিল: যে আপনি কিউবের পৃষ্ঠের ক্ষেত্রফলের চেয়ে বেশি ভালো কিছু করতে পারবেন না।

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

"জ্যামিতিতে অনেক সম্ভাবনা রয়েছে," মিনজার বলেছিলেন। "এটা ঠিক যে আমরা এটি যথেষ্ট ভাল বুঝতে পারি না।"