কম্পিউটার বিজ্ঞানে ১৯৬২ সালের একটি প্রাচীর ভাঙল

হ্যামিল্টনীয় চক্র হলো কোনো জালের মধ্য দিয়ে এমন একটি পূর্ণ পরিক্রমা, যা প্রতিটি বিন্দুতে ঠিক একবার যায় এবং শুরুর বিন্দুতে ফিরে আসে। একটি নির্দেশিত (ডিরেক্টেড) জালে প্রতিটি সংযোগ একটি তির, যা কেবল একদিকেই অনুসরণ করা যায়, ঠিক একমুখী রাস্তার মতো। এই সমস্যার ওজনযুক্ত রূপ হলো অপ্রতিসম ভ্রাম্যমাণ বিক্রেতা সমস্যা (asymmetric travelling salesman problem)।

এমন চক্র আছে কি না তা নির্ধারণ করা পাঠ্যবইয়ের একটি কঠিন সমস্যা। ১৯৬২ সালে রিচার্ড বেলম্যান এবং স্বাধীনভাবে মাইকেল হেল্ড ও রিচার্ড কার্প ডায়নামিক প্রোগ্রামিং অ্যালগরিদম দেন, যা n বিন্দুর একটি জালের জন্য প্রায় ২ⁿ সময়ে এটি সমাধান করে (কেবল বহুপদী হারে বাড়া গুণকগুলো বাদে)। ষাট বছরেরও বেশি সময় ধরে, সাধারণ নির্দেশিত জালে কেউই মৌলিকভাবে এর চেয়ে ভালো কিছু করতে পারেননি।

অনির্দেশিত জ্ঞাতি-ভাইটি আগেই হার মেনেছিল

দ্বিমুখী সংযোগের জালের জন্য আন্দ্রেয়াস বিয়র্কলুন্ড ২০১৪ সালে ১.৬৫৭ⁿ-এ চলা একটি দৈবায়িত অ্যালগরিদম দিয়ে প্রাচীরটি ভেঙেছিলেন; গবেষণাপত্র অনুযায়ী, এই কাজের জন্য তিনি ২০১৬ সালের EATCS–IPEC নেরোড পুরস্কার পান। সাধারণ অনির্দেশিত জালের জন্য এটি এখনো জানা দ্রুততম। নির্দেশিত জালের ক্ষেত্রে অগ্রগতি এসেছে কেবল বিশেষ ক্ষেত্রে — দ্বিবিভাজিত (বাইপারটাইট) জাল, প্রতি বিন্দুতে অল্প সংযোগের জাল — অথবা একটি অপ্রমাণিত অনুমানের ভিত্তিতে, স্ট্রাসেনের অসীমতটীয় র‍্যাংক অনুমান (asymptotic rank conjecture)।

নতুন সীমা

টোকিও বিশ্ববিদ্যালয়ের তোমোহিরো কোয়ানা এবং টোকিওর কোম্পানি CyberAgent-এর সোহ কুমাবে এখন একটি দৈবায়িত অ্যালগরিদম দিয়েছেন, যা নির্দেশিত সমস্যাটি নির্ধারণ করে এই সময়ে:

O((375/196)ⁿ) = O(1.9133ⁿ)**।

সাধারণ নির্দেশিত জালের জন্য, ১৯৬২ সালের পর এটি সূচকের ভিত্তিতে প্রথম উন্নতি।

জোড়-বিজোড়ে গোনা

কঠিনতাটি সূক্ষ্ম। চক্রগুলোকে মডুলো ২ গোনা — অর্থাৎ শুধু তাদের সংখ্যা জোড় না বিজোড় তা জানা — ২ⁿ-এর কম সময়ে আগেই সম্ভব ছিল। কিন্তু চক্রের একটি জোড়, অশূন্য সংখ্যা দেখতে হুবহু শূন্যের মতো। ধ্রুপদি সমাধান হলো সংযোগগুলোকে দৈব ওজন দেওয়া, যাতে কোনো এক মোট ওজনে একটি সমাধান অনন্য হয়ে যায় (বিচ্ছিন্নকরণ লেমা, isolation lemma); কিন্তু দ্রুত জোড়-বিজোড় গণনার পদ্ধতি ওজন সামলাতে পারত না।

লেখকদের কৌশল, সহজ ভাষায়:

1. চক্রের একটি তির অনুমান করুন, এবং তার বদলে সেই তিরের এক প্রান্ত থেকে অন্য প্রান্ত পর্যন্ত প্রতিটি বিন্দু ছুঁয়ে যাওয়া একটি পথ খুঁজুন।
2. প্রতিটি তিরকে ১/৫০ সম্ভাবনায় এলোমেলোভাবে মুছে ফেলুন।
3. প্রতিটি বিন্দুতে আগত তিরগুলোর তিনটি দল তৈরি করুন, এবং টিকে থাকা প্রতিটি তিরকে দলগুলোর একটি দৈব, অশূন্য সেটে নকল করুন।
4. যদি একটি পরিক্রমা থাকে, তবে অন্তত (49/50)ⁿ⁻¹ সম্ভাবনায় প্রতিটি বিন্দুর জন্য একটি করে দল এমনভাবে বেছে নেওয়া যায় যাতে বৈধ পথের সংখ্যা বিজোড় হয়।
5. প্রতিটি দলকে — প্রতিটি তিরকে নয় — একটি দৈব ওজন দিন। এবার বিচ্ছিন্নকরণের কৌশল কাজ করে, এবং প্রায় (50/49)ⁿ বার পুনরাবৃত্তিই যথেষ্ট।
6. প্রতিটি পুনরাবৃত্তি (15/8)ⁿ সময়ে প্রতিটি মোট ওজনে জোড়-বিজোড় গণনা বের করে, বিয়র্কলুন্ড, কাস্কি ও কুটিসের ম্যাট্রিক্স নির্ণায়কের যোগফল এবং আরবিন্দ ও গুরুস্বামীরও ব্যবহৃত একটি দৈব “রৈখিকীকরণ” কাজে লাগিয়ে।

দুটি গুণ করুন: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ।

যন্ত্রের তৈরি একটি প্রমাণ

গবেষণাপত্রটি শেষ হয়েছে জেনারেটিভ এআই সম্পর্কে একটি ঘোষণা দিয়ে: মূল উপপাদ্যের প্রমাণ তৈরি করেছে ChatGPT 6 Astra এবং পাণ্ডুলিপির খসড়া তৈরিতে সাহায্য করেছে। লেখকেরা মধ্যবর্তী প্রতিজ্ঞাগুলোর বিবৃতি দিয়েছেন, যা মডেলের মূল সমাধানের একটি সংযোগতাত্ত্বিক (কম্বিনেটোরিয়াল) পাঠ দেয়; তারপর সবকিছু যাচাই ও সংশোধন করেছেন, এবং পূর্ণ দায়িত্ব নিয়েছেন।

ফলাফলটি তাত্ত্বিক — কোনো প্রোগ্রাম চালানো হয়নি — এবং অ্যালগরিদমটি দৈবায়িত, যেকোনো দিকে ভুলের সামান্য সম্ভাবনাসহ। একমুখী রাস্তার ১.৯১৩৩ আর দ্বিমুখী রাস্তার ১.৬৫৭-এর মাঝে একটি বড় ফাঁক এখনো খোলা রয়ে গেছে।