কিছু চতুর্মাত্রিক আকৃতি কোনো অ্যালগরিদমই চিনতে পারে না

কিছু প্রশ্নের কোনো রেসিপি নেই। কেউ এখনো খুঁজে পায়নি বলে নয়, বরং এটা প্রমাণিত যে কোনো অ্যালগরিদম — কোনো ধাপে-ধাপে প্রক্রিয়া, তা যত দীর্ঘই হোক, যেকোনো কম্পিউটারে চালানো — প্রতিবার সেগুলোর সঠিক উত্তর দিতে পারে না। ইউনিভার্সিটি অব টেক্সাস অ্যাট অস্টিনের ক্যামেরন ম্যাক. গর্ডন (Cameron McA. Gordon) চতুর্মাত্রিক আকৃতি নিয়ে এমন আরও দুটি প্রশ্ন যোগ করেছেন।

এটি কি একই আকৃতি?

গণিতবিদেরা এই আকৃতিগুলোকে বলেন 4-ম্যানিফোল্ড (4-manifolds): এমন স্থান, যা কাছ থেকে দেখলে সর্বত্র সাধারণ চতুর্মাত্রিক স্থানের মতো দেখায়। এগুলো কম্পিউটারের হাতে তুলে দিতে গবেষণাপত্রটি ধরে নেয় যে এগুলো জোড়া লাগানো সমতল টুকরো দিয়ে গড়া (“খণ্ডশ রৈখিক”, piecewise linear, বা PL), যাতে প্রতিটিকে উপাত্তের একটি সসীম তালিকা দিয়ে বর্ণনা করা যায়। মৌলিক প্রশ্নটি তখন দাঁড়ায়: এমন দুটি আকৃতি দেওয়া থাকলে, অবিচ্ছিন্ন বিকৃতির পার্থক্য উপেক্ষা করলে, এরা কি একই?

1958 সালে এ. এ. মার্কভ (A. A. Markov) দেখান যে এই প্রশ্নের কোনো অ্যালগরিদম নেই। মার্কভের প্রমাণ আকৃতির সমস্যাটিকে গ্রুপ (group) নিয়ে একটি সমস্যায় পরিণত করে: সসীমসংখ্যক নিয়ম দিয়ে সংজ্ঞায়িত এমন গ্রুপ আছে, যাদের ক্ষেত্রে কোনো অ্যালগরিদম নির্ধারণ করতে পারে না যে তাদের উপাদানগুলোর একটি প্রদত্ত সমাবেশ অভেদকের (identity) সমান কি না — “শব্দ সমস্যা” (word problem)। এমন একটি গ্রুপ থেকে এমন আকৃতি গড়া যায়, যেগুলোকে কোনো অ্যালগরিদম আলাদা করে চিনতে পারত কেবল সেই অসম্ভব সমস্যাটি সমাধান করেই।

গুনতে গুনতে সাতে

মার্কভের যুক্তি কাঠিন্যটিকে এমনকি নির্দিষ্ট আকৃতিতে বেঁধে দেয়। নিন S², একটি সাধারণ বলের পৃষ্ঠতল, এবং গঠন করুন গুণফল S² × S², একটি চতুর্মাত্রিক আকৃতি। এর k টি কপি জোড়া লাগান (একটি “সংযুক্ত যোগফল”, connected sum, লেখা হয় #k)। কিছু k-এর জন্য কোনো অ্যালগরিদম নির্ধারণ করতে পারে না যে একটি প্রদত্ত আকৃতি #k(S² × S²) কি না। কোন k?

গবেষণাপত্রটি এই কমে আসার ইতিহাস তুলে ধরে। 1969 সালে বরিসভের (Borisov) খুঁজে পাওয়া, অমীমাংস্য শব্দ সমস্যা ও 12টি নিয়মসহ একটি গ্রুপ দিয়েছিল 14টি কপি। গর্ডন 2022 সালে তা নামান 12-তে। এম. ট্যান্সার (M. Tancer) একটি নতুন পথ খুঁজে পান, চতুর্মাত্রিক আকৃতির ফ্রিডম্যানের (Freedman) শ্রেণিবিন্যাসের মধ্য দিয়ে, এবং “টপোলজিক্যাল” সংস্করণে পৌঁছান 9-এ, যেখানে আকৃতিগুলোকে সমতল টুকরো দিয়ে গড়া হতে হয় না। এই কাজের একটি আগের সংস্করণ পৌঁছেছিল 8-এ। তারপর কেগেল (Kegel), লি (Li) ও রেন (Ren) অনেক ছোট একটি অমীমাংস্য গ্রুপ গড়েন — 3টি জনক (generators) ও 9টি নিয়ম — যা টপোলজিক্যাল সংস্করণে পৌঁছায় 7-এ এবং সমতল-টুকরো সংস্করণে 9-এ।

গর্ডন ট্যান্সারের পথটিকে সমতল টুকরো দিয়ে গড়া আকৃতির জন্যও কার্যকর করেন, এবং প্রমাণ করেন:

একটি প্রদত্ত 4-ম্যানিফোল্ড S² × S²-এর 7টি কপির সংযুক্ত যোগফলের সঙ্গে টুকরো ধরে ধরে একই কি না, তা নির্ধারণ করার কোনো অ্যালগরিদম নেই।

প্রমাণের কেন্দ্রে আছে একটি অভিধান। কেগেল, লি ও রেনের গ্রুপের প্রতিটি শব্দ w-এর জন্য গর্ডন একটি চতুর্মাত্রিক আকৃতি গড়েন। w যদি অভেদকের সমান হয়, তাহলে নিয়মগুলোর ওপর অনুমোদিত চালের একটি অনুক্রম — অ্যান্ড্রুজ-কার্টিস চাল (Andrews-Curtis moves), যা আকৃতিটি না বদলে তার বর্ণনা নতুন করে লেখে — দেখিয়ে দেয় যে আকৃতিটি ঠিক S² × S²-এর সাতটি কপি। তা না হলে, আকৃতিটিতে এমন লুপ থাকে যা টেনে একটি বিন্দুতে গুটিয়ে আনা যায় না — যা S² × S²-এর সাতটি কপিতে কখনো ঘটে না — তাই এটি ওই সাতটি কপি হতে পারে না। তাই #7(S² × S²)-কে চিনতে পারা একটি অ্যালগরিদম শব্দ সমস্যার সমাধান করে ফেলত, যা অসম্ভব।

গিঁট-বাঁধা গোলক

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

গর্ডন প্রমাণ করেন যে #7(S² × S²)-এর ভেতরে একটি দ্বিমাত্রিক গোলক — বা যেকোনো পৃষ্ঠতল, অভিমুখযোগ্য হোক বা না হোক — গিঁটহীন কি না, তা নির্ধারণের কোনো অ্যালগরিদম নেই। পথে গবেষণাপত্রটি ওই আকৃতিতে এমন একটি গোলক গড়ে, যার চারপাশের স্থানের গ্রুপের শব্দ সমস্যা অমীমাংস্য, এবং S² × S²-এর 12টি কপিতে এমন একটি গোলক, যার গ্রুপে কম্পিউটার দিয়ে বর্ণনা করা যায় এমন প্রতিটি গ্রুপের একটি করে কপি রয়েছে।

পুরস্কার: শূন্য কপি

গবেষণাপত্রটি লক্ষ্যটি সোজাসুজি বলে: কপির সংখ্যা শূন্যে নামিয়ে আনা। শূন্য কপি মানে চতুর্মাত্রিক গোলক S⁴ নিজেই। পাঁচ বা তার বেশি মাত্রায় কোনো অ্যালগরিদম গোলককে চিনতে পারে না; দুই ও তিন মাত্রায় একটি অ্যালগরিদম পারে। চার মাত্রা খোলা রয়ে গেছে — আর খোলা রয়ে গেছে S⁴-এর ভেতরের গিঁট-বাঁধা গোলক শনাক্ত করা যায় কি না, সেই প্রশ্নও। প্রতিটি কপি সরানো দুটি প্রশ্নকেই আরও কাছে নিয়ে আসে।