২২ বছরের সন্দেহের পর: বার্তা মেশানো পথে পাঠানোকে হারাল

কেবলের একটি নেটওয়ার্কের কথা ভাবুন, যেখানে কয়েকজন প্রেরক প্রত্যেকে নিজের প্রাপকের কাছে পৌঁছাতে চায়। চিরাচরিত পদ্ধতি হলো রাউটিং (routing): প্রতিটি বার্তা পার্সেলের মতো এক বা একাধিক পথে চলে, আর ট্র্যাফিক যেকোনো অনুপাতে অনেক পথে ভাগও করা যায়। নেটওয়ার্ক কোডিং (network coding) আরেকটি স্বাধীনতা যোগ করে: মাঝের নোডগুলো প্রাপ্ত বার্তা শুধু এগিয়ে না দিয়ে সেগুলোকে মিলিয়ে দিতে পারে — যেমন যোগ করে।

প্রশ্ন হলো, এই স্বাধীনতা কি কখনও বেশি তথ্য পার হতে দেয়। গবেষণাপত্রটি অনির্দেশিত (undirected) নেটওয়ার্কে মনোযোগ দেয়, যেখানে একটি কেবল যেকোনো দিকে তথ্য বইতে পারে, কিন্তু দুই দিক একটিই ধারণক্ষমতা ভাগ করে নেয়।

একের পর এক ক্ষেত্রে সত্য প্রমাণিত একটি অনুমান

২০০৪ সালে লি ও লি (Li and Li) অনুমান করেন যে এই পরিস্থিতিতে ভগ্নাংশ রাউটিংয়ের তুলনায় কোডিং কোনো সুবিধা দেয় না; হার্ভি, ক্লাইনবার্গ ও রাসালা লেহম্যান (Harvey, Kleinberg and Rasala Lehman) স্বাধীনভাবে একই অনুমান করেন। পরের দুই দশকে এটি একের পর এক শ্রেণির নেটওয়ার্কে সত্য প্রমাণিত হয় — দুটি সেশন, কিছু সমতলীয় নেটওয়ার্ক, সর্বাধিক ছয়টি কোডিং নোডের নেটওয়ার্ক, এবং আরও — কিন্তু সাধারণভাবে কখনও মীমাংসা হয়নি। জটিলতা-তত্ত্বের অন্য কিছু ফলাফল, যেমন বাহ্যিক মেমোরিতে পূর্ণসংখ্যা সাজানো ও গুণন-সার্কিটের নিম্নসীমা, এমনকি একে সত্য ধরে নিয়েই প্রমাণ করা হয়েছিল।

জানা তত্ত্ব আগেই বাজির আকার সীমিত করে দিয়েছিল: কোডিং রাউটিংকে বড়জোর একটি লগারিদমীয় গুণক পরিমাণ হারাতে পারে। আর ব্রেভারম্যান, গার্গ ও শোয়ার্ৎসম্যানের (Braverman, Garg and Schvartzman) ২০১৭ সালের একটি ফলাফল দেখিয়েছিল যে কঠোর কোডিং-সুবিধাসম্পন্ন একটিমাত্র নেটওয়ার্ককে বিবর্ধিত করে অনেক বড় ব্যবধান তৈরি করা যায়। সবকিছু নির্ভর করছিল একটি সসীম উদাহরণ খুঁজে পাওয়ার ওপর।

যোগ করাই যথেষ্ট

পরিশিষ্টে মৌলিক কৌশলটি দেওয়া আছে, যা দেখায় মেশানো কেন সাহায্য করতে পারে। কয়েকটি উৎসকে একটি কেন্দ্র v-এর চারপাশে রাখুন, তাদের প্রাপকদের আরেকটি কেন্দ্র w-এর চারপাশে, আর v ও w-কে একটি কেবলে যুক্ত করুন। প্রতিটি উৎসের অন্য প্রাপকদের দিকে ছোট পার্শ্বপথও আছে। তিন দফায় মাঝের কেবলটি সব বার্তার যোগফল বহন করে; প্রতিটি প্রাপক সেই যোগফল আর পার্শ্বপথ থেকে বাকি বার্তাগুলো পায়, এবং বিয়োগ করে নিজের বার্তাটি উদ্ধার করে। মাঝের কেবল ছাড়া প্রতিটি উৎস তার প্রাপক থেকে পাঁচ ধাপ (hop) দূরে।

হয়েপলার, ওয়াজক ও জুজিকের (Haeupler, Wajc and Zuzic) আগের কাজ থেকে আসা এই কৌশল কোডিংকে দ্রুততর করে, কিন্তু একা একা বেশি বহন করার ক্ষমতা দেয় না: একটি লম্বা পথও উচ্চ হারের পাইপলাইন চালাতে পারে।

নেটওয়ার্কে রূপান্তরিত একটি সার্কিট

টরন্টো বিশ্ববিদ্যালয়ের শিনদান ঝাং (Xindan Zhang) ও বাওচুন লি (Baochun Li), এবং সিংহুয়া বিশ্ববিদ্যালয়ের জংপেং লি (Zongpeng Li) হারিয়ে যাওয়া ধাপটি খুঁজে পান। তাঁরা একটি ছোট কোডকে একটি বিপরীতযোগ্য গণনায় (reversible computation) রূপান্তর করেন — বিপরীতযোগ্য পূর্ণসংখ্যা-যোগের একটি সার্কিট, যা গণনা করে, ফলাফলের প্রতিলিপি তৈরি করে, তারপর মাঝের কাজগুলো উল্টে দেয়। এরপর তাঁরা একটি নতুন নেটওয়ার্ক তৈরি করেন যার ভৌত কেবলগুলোই সেই সার্কিটের তার, এবং গণনার প্রতিটি রেজিস্টারকে, অস্থায়ী (scratch) রেজিস্টারসহ, তার নিজস্ব প্রেরক-প্রাপক চাহিদা দেন।

তার বরাবর “সময়ের” একটি সতর্ক হিসাব বাকি কাজটা করে দেয়। সব তারের ওপর যোগ করলে দৈর্ঘ্যগুলো ঠিক সেই ন্যূনতম দূরত্বের সমান হয়, যা চাহিদাগুলোকে অতিক্রম করতে হবে। কিন্তু নির্ধারিত চাহিদাগুলো এমন কিছু গেট এড়াতে পারে না, যেগুলোর খরচ দুই একক বেশি। তাই রাউটিংকে পূর্ণ হারের চেয়ে কঠোরভাবে পিছিয়ে থাকতে হয়, অথচ কোডটি প্রতিটি কেবল ঠিক একবার ব্যবহার করে এবং অনেক ব্লকে পাইপলাইন করলে এক-এর হারের কাছাকাছি পৌঁছায়।

কী প্রমাণিত হয়েছে

একটি সসীম সংযুক্ত নেটওয়ার্ক, যেখানে প্রতিটি নোড বড়জোর আরও তিনটির সঙ্গে যুক্ত এবং প্রতিটি কেবলের ধারণক্ষমতা এক একক, যার ওপর একটি সরল বাইনারি রৈখিক কোড সম্ভাব্য সেরা ভগ্নাংশ রাউটিংকে হারায়। ২০০৪ সালের অনুমানটি ভুল।
একই পূর্ণসংখ্যা-নির্মাণ একসঙ্গে প্রতিটি সসীম ক্ষেত্র (finite field) এবং প্রতিটি অতুচ্ছ সসীম অ্যাবেলীয় গ্রুপের ওপর কাজ করে।
প্রতিলিপিগুলো বারবার মিলিয়ে লেখকেরা নেটওয়ার্কের অসীম পরিবার তৈরি করেন, যেখানে কোডিং পূর্ণ হারের কাছাকাছি পৌঁছায় আর রাউটিং 1/log n-এর কোনো ঘাতের মতো কমে যায় — একটি বহুলগারিদমীয় (polylogarithmic) সুবিধা।

গবেষণাপত্রটি তার প্রতি-উদাহরণে নোডের সংখ্যা জানায় না। এর মৌলিক খণ্ডটি একাই এমন একটি কোড, যা ১৩,১২২ দফা ধরে চলে।

মেশিনে যাচাই করা

সসীম প্রতি-উদাহরণ ও পরিবার-উপপাদ্য, দুটোকেই Lean প্রুফ অ্যাসিস্ট্যান্টে আনুষ্ঠানিক রূপ দেওয়া হয়েছে। লেখকদের মতে, ২,৪৭২টি ঘোষণা ও ১,৭৫৫টি উপপাদ্যের একটি নিরীক্ষা দেখায় যে প্রমাণগুলো কেবল Lean-এর তিনটি মানক স্বতঃসিদ্ধ ব্যবহার করে, কোনো অসম্পূর্ণ প্রমাণ নেই; একটি নতুন পরিবেশে স্বাধীন পুনর্যাচাইও সফল হয়েছে, যদিও একই Lean কার্নেল দিয়ে।

কী এখনও খোলা

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

এআই ব্যবহারের ঘোষণা। একটি পাদটীকায় বলা হয়েছে যে OpenAI-এর GPT-6 Astra প্রমাণ ও Lean কোড তৈরিতে সহায়তা করেছে।