জটিলতা তত্ত্বের জ্ঞানের সীমার দিকে 50-বছরের যাত্রা | কোয়ান্টা ম্যাগাজিন

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

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

"আমি 100% বুঝতে পারিনি," কারমোসিনো বলেছিলেন। "কিন্তু আমি জানতাম যে আমি চাই।"

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

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

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

মনে হচ্ছে যে গণনাগত সমস্যাগুলি সমাধান করা কঠিন তা প্রমাণ করা নিজেই একটি কঠিন কাজ। কিন্তু এত কষ্ট কেন? এবং ঠিক কতটা কঠিন? কারমোসিনো এবং মেটা-জটিলতার সাবফিল্ডের অন্যান্য গবেষকরা এই ধরনের প্রশ্নগুলিকে কম্পিউটেশনাল সমস্যা হিসাবে তুলে ধরেন, জটিলতা তত্ত্বের লেন্সকে নিজের দিকে ফিরিয়ে নিয়ে ক্ষেত্রটিকে এগিয়ে নিয়ে যান।

"আপনি ভাবতে পারেন, 'ঠিক আছে, এটা চমৎকার। হয়তো জটিলতা তাত্ত্বিকরা পাগল হয়ে গেছে,' বলেন রাহুল ইলাঙ্গো, MIT-এর একজন স্নাতক ছাত্র যিনি ক্ষেত্রের সবচেয়ে উত্তেজনাপূর্ণ সাম্প্রতিক ফলাফলগুলি তৈরি করেছেন।

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

"এটা স্পষ্ট হয়ে গেছে যে মেটা-জটিলতা জিনিসের হৃদয়ের কাছাকাছি," বলেন স্কট অ্যারনসন, অস্টিনের টেক্সাস বিশ্ববিদ্যালয়ের একজন জটিলতা তত্ত্ববিদ।

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

জানা অজানা

পি বনাম এনপি সমস্যাটি জটিলতা তাত্ত্বিকদের গণনাগত সমস্যাগুলিকে বিস্তৃত আকারে সাজানোর অভ্যাসের জন্য এর অপ্রতুল নামকে দায়ী করে।জটিলতা ক্লাস” Nasdaq টিকার চিহ্নের ইঙ্গিতপূর্ণ লেবেল সহ। একটি কম্পিউটেশনাল সমস্যা হল একটি যা নীতিগতভাবে একটি অ্যালগরিদম দ্বারা সমাধান করা যেতে পারে - নির্দেশাবলীর একটি সুনির্দিষ্টভাবে নির্দিষ্ট তালিকা। কিন্তু সমস্ত অ্যালগরিদম সমানভাবে উপযোগী নয়, এবং অ্যালগরিদমের মধ্যে পার্থক্য বিভিন্ন শ্রেণীর সমস্যার মধ্যে মৌলিক পার্থক্যের ইঙ্গিত দেয়। জটিলতা তত্ত্ববিদদের জন্য চ্যালেঞ্জ হল এই ইঙ্গিতগুলিকে জটিলতা শ্রেণীর মধ্যে সম্পর্ক সম্পর্কে কঠোর উপপাদ্যে পরিণত করা।

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

"P" এবং "NP" হল a এর সবচেয়ে বিখ্যাত দুটি সদস্য ক্রমবর্ধমান যন্ত্রণা শত শত জটিলতার ক্লাস। মোটামুটিভাবে বলতে গেলে, P হল সমস্যার একটি শ্রেণী যা সহজেই সমাধান করা যায়, যেমন একটি তালিকার বর্ণমালা। NP হল সুডোকু পাজলের মত সহজে পরীক্ষাযোগ্য সমাধান সহ সমস্যার শ্রেণী। যেহেতু সমস্ত সহজে সমাধানযোগ্য সমস্যাগুলি পরীক্ষা করাও সহজ, তাই P-এর সমস্যাগুলি NP-তেও রয়েছে। কিন্তু কিছু এনপি সমস্যা সমাধান করা কঠিন বলে মনে হচ্ছে — আপনি প্রথমে অনেক সম্ভাবনার চেষ্টা না করে একটি সুডোকু ধাঁধার সমাধানটি অবিলম্বে বুঝতে পারবেন না। এটা কি হতে পারে যে এই আপাত কঠোরতা শুধুমাত্র একটি বিভ্রম - যে প্রতিটি সহজে পরীক্ষাযোগ্য সমস্যা সমাধানের জন্য একটি একক সহজ কৌশল আছে?

যদি তাই হয়, তাহলে P = NP: দুটি শ্রেণী সমতুল্য। যদি তা হয়, তাহলে এমন কিছু অ্যালগরিদম থাকতে হবে যা বিশাল সুডোকু ধাঁধা সমাধান করা, গ্লোবাল শিপিং রুট অপ্টিমাইজ করা, অত্যাধুনিক এনক্রিপশন ভাঙতে এবং গাণিতিক উপপাদ্যগুলির প্রমাণগুলি স্বয়ংক্রিয়ভাবে তুচ্ছ করে তোলে৷ যদি P ≠ NP হয়, তাহলে অনেক কম্পিউটেশনাল সমস্যা যা নীতিগতভাবে সমাধানযোগ্য, বাস্তবে আমাদের ধরার বাইরে চিরকাল থাকবে।

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

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

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

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

তারপরে 1936 সালে, অ্যালান টুরিং নামে একজন 23 বছর বয়সী স্নাতক ছাত্র হিলবার্টের সিদ্ধান্তযোগ্যতার অবস্থাকে গণনার তখনকার অপরিচিত ভাষায় পুনরায় ব্যাখ্যা করেছিলেন এবং এটিকে একটি মারাত্মক আঘাত করেছিলেন। টুরিং একটি গাণিতিক মডেল প্রণয়ন করেছিলেন — যা এখন নামে পরিচিত টুরিং মেশিন — যা সমস্ত সম্ভাব্য অ্যালগরিদম উপস্থাপন করতে পারে, এবং দেখিয়েছে যে যদি হিলবার্টের পদ্ধতি বিদ্যমান থাকে তবে এটি এই মডেলের মধ্যে মাপসই হবে। তারপর তিনি Gödel's এর মত স্ব-রেফারেন্সিয়াল পদ্ধতি ব্যবহার করেন প্রমাণ করা অনির্ধারিত বিবৃতির অস্তিত্ব — বা, সমতুল্যভাবে, গণনাযোগ্য সমস্যা যা কোনো অ্যালগরিদম সমাধান করতে পারেনি।

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

1960-এর দশকে, কম্পিউটার বিজ্ঞানীরা কিছু সমস্যা সমাধানের জন্য দ্রুত অ্যালগরিদম তৈরি করেছিলেন, অন্যদের জন্য শুধুমাত্র পরিচিত অ্যালগরিদমগুলি ছিল অত্যন্ত ধীর। যদি প্রশ্নটি কেবল সমস্যাগুলি সমাধানযোগ্য কিনা তা নয়, তবে সেগুলি সমাধান করা কতটা কঠিন?

"একটি সমৃদ্ধ তত্ত্ব আবির্ভূত হয়, এবং আমরা আর উত্তরগুলি জানি না," কারমোসিনো বলেছিলেন।

ভিন্নমুখী পথ

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

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

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

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

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

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

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

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

সার্বজনীনভাবে কঠিন

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

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

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

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

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

যেকোন NP-সম্পূর্ণ সমস্যার অসুবিধা নিষ্পত্তি করা P বনাম NP প্রশ্নের সমাধান করার জন্য যথেষ্ট হবে। যদি P ≠ NP হয়, সহজ এবং কঠিন সমস্যার মধ্যে পার্থক্য হাজার হাজার কলাম দ্বারা ধরে রাখা হয় যেগুলি সবই সমান শক্তিশালী। যদি P = NP হয়, পুরো ভবনটি ধসে পড়ার দ্বারপ্রান্তে, শুধু একটি টুকরো পড়ার অপেক্ষায়।

কুক, লেভিন এবং কার্প একত্রিত করেছিলেন যা অনেকগুলি সম্পর্কহীন সমস্যার মতো মনে হয়েছিল। এখন সমস্ত জটিলতা তাত্ত্বিকদের একটি সমস্যা সমাধান করতে হয়েছিল: P = NP কি না?

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

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

এখন ধরুন যে P ≠ NP. এটি প্রমাণ করা আরও কঠিন বলে মনে হচ্ছে। জটিলতা তাত্ত্বিকদের প্রতিষ্ঠিত করতে হবে যে কোনও দ্রুত অ্যালগরিদম সম্ভবত বিদ্যমান থাকতে পারে না, কার্যকরভাবে সমস্ত ভবিষ্যতের গবেষকদের সর্বোত্তম প্রচেষ্টাকে প্রত্যাশিত এবং ব্যর্থ করে।

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

কলেজে কারমোসিনোর শেষ বছরে, তার কৌতূহল তাকে গোডেল থেকে জটিলতা তত্ত্বের স্নাতক কোর্সে নিয়ে যায়। তিনি বুঝতে পেরে অবাক হয়েছিলেন যে তিনি তার প্যাশন প্রকল্পের চেয়ে হোমওয়ার্কে বেশি সময় ব্যয় করছেন, একটি কম্পিউটার প্রোগ্রাম যা রূপকথার আখ্যান গঠন শিখবে এবং নতুনগুলি তৈরি করবে।

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

"তিনি এমন ছিলেন, 'আপনি জানেন, আপনি যদি এটি চালিয়ে যেতে চান, যদি আপনি তাত্ত্বিক কম্পিউটার বিজ্ঞান এবং জটিলতা তত্ত্ব চালিয়ে যেতে চান, আপনি করতে পারেন: এটিকে গ্র্যাড স্কুল বলা হয়,'" কার্মোসিনো বলেছিলেন। তার মাস্টার্স পাওয়ার পর, তিনি 2012 সালে ইম্পাগ্লিয়াজোর তত্ত্বাবধানে ডক্টরেটের দিকে কাজ করার জন্য সান দিয়েগোতে চলে যান।

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

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

"জটিলতা তত্ত্ব অভিশপ্ত এবং অনেক বাধা দিয়ে আশীর্বাদ করা হয়," ইলাঙ্গো বলেন।

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

কিন্তু মেটা-জটিলতার প্রাকৃতিক প্রমাণের বাধা থেকে পথ অনুসরণ করার জন্য, আমাদের 1970-এর দশকে গবেষকরা যেখানে প্রথমবার P বনাম এনপি সমস্যা মোকাবেলা করতে শুরু করেছিলেন সেখানে ফিরে যেতে হবে। কি সমস্যা কঠিন প্রমাণ করা এত কঠিন?

একটি বৃত্তাকার পথ

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

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

এই এক্সপ্রেশনগুলিতে, বুলিয়ান ভেরিয়েবলগুলিকে "লজিক গেটস" এবং, বা এবং না দ্বারা একসাথে সংযুক্ত করা হয়েছে। প্রাথমিক অভিব্যক্তি A এবং B, উদাহরণস্বরূপ, যখন A এবং B উভয়ই সত্য হয় এবং অন্যথায় মিথ্যা হয়; অন্যদিকে A OR B সত্য হয় যদি দুটি চলকের মধ্যে অন্তত একটি সত্য হয়। একটি নট গেট আরও সহজ: এটি একটি একক ভেরিয়েবলের মানকে উল্টে দেয়। এই মৌলিক বিল্ডিং ব্লকগুলির পর্যাপ্ত সাথে, আপনি যে কোনও গণনা করতে পারেন।

“যখন আপনি আপনার কম্পিউটারের দিকে তাকান, দিনের শেষে, এটি কী করছে? এটা একটা সার্কিট চালাচ্ছে,” ইলাঙ্গো বলল।

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

সার্কিট জটিলতা কাঠামোর জন্য টুরিংয়ের গণনার মডেলের সবচেয়ে মৌলিক ধারণাগুলি পুনর্বিবেচনা করা প্রয়োজন। এখানে, কম্পিউটেশনাল সমস্যা এবং তাদের সমাধানকারী অ্যালগরিদমগুলির পরিবর্তে, গবেষকরা বুলিয়ান ফাংশন এবং তাদের গণনাকারী সার্কিটগুলি বিবেচনা করেন। একটি বুলিয়ান ফাংশন বুলিয়ান ভেরিয়েবল - trues এবং falses, 1s এবং 0s - এবং আউটপুট সত্য বা মিথ্যা, 1 বা 0 গ্রহণ করে। এবং একটি অ্যালগরিদমের মতো, একটি সার্কিট যেকোন ইনপুট দেওয়া আউটপুট তৈরি করার পদ্ধতি বর্ণনা করে।

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

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

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

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

1980-এর দশকে বেশিরভাগ জটিলতা তত্ত্ববিদরা এই কৌশলটি অনুসরণ করেছিলেন। এবং মতভেদ তাদের পক্ষে ছিল। শ্যানন ছিল প্রতিপন্ন 1949 সালে প্রায় প্রতিটি বুলিয়ান ট্রুথ টেবিলে (যা নির্দিষ্ট আকারের বুলিয়ান ফাংশনের সমস্ত সম্ভাব্য ইনপুট এবং আউটপুটগুলির একটি দীর্ঘ তালিকা মাত্র) সার্কিট জটিলতা রয়েছে যা কার্যত যতটা সম্ভব বেশি। তিনি একটি অত্যাশ্চর্য সহজ যুক্তি ব্যবহার করেছিলেন: অনেকগুলি গেটকে একত্রিত করার উপায়গুলির তুলনায় অল্প সংখ্যক গেটকে একত্রিত করার অনেক কম উপায় রয়েছে।

"এখানে চারপাশে যাওয়ার জন্য যথেষ্ট ছোট সার্কিট নেই," অ্যারনসন বলেছিলেন।

তাই জটিলতা তাত্ত্বিকরা একটি কৌতূহলী পরিস্থিতিতে নিজেদের খুঁজে পেয়েছেন। যদি প্রায় প্রতিটি সত্য টেবিলে উচ্চ সার্কিট জটিলতা থাকে, তাহলে প্রায় প্রতিটি বুলিয়ান ফাংশন গণনা করা কঠিন হতে হবে। গবেষকদের কেবলমাত্র এমন একটি একক ফাংশন সনাক্ত করতে হয়েছিল যা এনপি শ্রেণিতেও পরিচিত ছিল। যে কত কঠিন হতে পারে?

ক্রিপ্টো ব্রোস

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

"কল্পনাটি ছিল যে আপনি এই সীমাবদ্ধ মডেলগুলি সম্পর্কে জিনিসগুলি প্রমাণ করতে সক্ষম হবেন, এবং তারপরে আপনি কম এবং কম বিধিনিষেধের সাথে কাজ করতে শিখেছেন তা তৈরি করতে পারবেন," সিপসার বলেছিলেন।

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

"আমি ভাগ্যবান ছিলাম যে আমি জানতাম না যে এই সমস্যাটি কতটা কঠিন," রাজবোরভ বলেছিলেন। "অন্যথায় আমি হয়তো শুরুই করতাম না।"

Razborov শুধুমাত্র AND এবং OR গেট ধারণকারী সার্কিট বিশ্লেষণ করেছেন, এবং প্রতিপন্ন একটি নির্দিষ্ট ফাংশন এই ধরনের সার্কিট ব্যবহার করে গণনা করা কঠিন ছিল, গেটগুলি যেভাবেই সাজানো হোক না কেন - আরও কী, সেই ফাংশনটি NP-সম্পূর্ণ বলে পরিচিত ছিল। P বনাম NP সমাধান করার জন্য সমস্ত গবেষকদের করতে হয়েছিল Razborov এর কৌশলগুলিকে NOT গেট সহ সার্কিটগুলিতে প্রসারিত করা হয়েছিল।

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

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

"আমাদের কৌতুক ছিল আমরা একটি বোতাম পেতে যাচ্ছি যা 'স্ব-রেফারেন্স' বলে," ইম্পাগ্লিয়াজো বলেছিলেন।

স্নাতক ছাত্র হিসাবে, রুডিচ এবং ইম্পাগ্লিয়াজো উভয়েই ক্রিপ্টোগ্রাফির জটিলতা-তাত্ত্বিক ভিত্তির উপর কাজ করেছেন, এমন একটি বিষয় যা P ≠ NP প্রমাণ করার চেষ্টা করার জন্য সম্ভবত সর্বোত্তম ব্যবহারিক প্রেরণা প্রদান করে। ক্রিপ্টোগ্রাফাররা গোপন বার্তাগুলিকে "সিউডোর্যান্ডমনেস" এ ক্লোক করে লুকিয়ে রাখে — এইভাবে এনক্রিপ্ট করা একটি বার্তা যেকোন ইভড্রপারের কাছে সংখ্যার এলোমেলো গোলমালের মতো দেখাবে, তবে এটি এখনও উদ্দিষ্ট প্রাপকের দ্বারা ডিকোড করা যেতে পারে। কিন্তু আপনি কীভাবে নিশ্চিত হতে পারেন যে একজন ইভসড্রপার কোডটি ভাঙতে খুব কঠিন মনে করবে?

এখানেই জটিলতা তত্ত্ব আসে৷ বর্তমানে যে এনক্রিপশন পদ্ধতিগুলি সবচেয়ে বেশি ব্যবহৃত হয় তা সবই আপাতদৃষ্টিতে কঠিন NP সমস্যার উপর ভিত্তি করে — বার্তাটি ডিক্রিপ্ট করার জন্য, একজন আক্রমণকারীর সমস্যা সমাধানের জন্য একটি এখনও অনাবিষ্কৃত দ্রুত অ্যালগরিদম প্রয়োজন৷ এই পদ্ধতিগুলি সত্যই সুরক্ষিত তা প্রতিষ্ঠিত করতে, আপনাকে একটি জিনিস প্রমাণ করতে হবে যে P ≠ NP। একটি প্রমাণ ছাড়াই, সিপসার বলেছিলেন, আপনি যা করতে পারেন তা হল "আশা করি যে আপনি যার কাছ থেকে গোপন রাখার চেষ্টা করছেন তিনি আপনার চেয়ে ভাল গণিতবিদ নন।"

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

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

একটি নিষ্ঠুর রসিকতা

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

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

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

"আপনি প্রায় সাহায্য করতে পারবেন না কিন্তু আপনি যে জন্য দর কষাকষি করেছেন তার চেয়ে বেশি পেতে পারেন," কারমোসিনো বলেছিলেন।

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

এই সংযোগটি বোঝার জন্য, অনেক ইনপুট ভেরিয়েবল সহ একটি বুলিয়ান ফাংশনের সত্য সারণীতে আউটপুট কলামটি দেখার কল্পনা করুন এবং প্রতিটি "সত্য" 1 দিয়ে এবং প্রতিটি "মিথ্যা" 0 দিয়ে প্রতিস্থাপন করুন:

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

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

অন্যদিকে, যদি নিরাপদ ক্রিপ্টোগ্রাফি সম্ভব হয়, তাহলে প্রাকৃতিক প্রমাণগুলি P ≠ NP প্রমাণ করার জন্য একটি কার্যকর কৌশল নয় — সুরক্ষিত ক্রিপ্টোগ্রাফির একটি পূর্বশর্ত। সংক্ষেপে এটাই প্রাকৃতিক প্রমাণ বাধা। দেখে মনে হচ্ছিল যেন জটিলতা তাত্ত্বিকরা একটি নিষ্ঠুর রসিকতার প্রাপ্তির প্রান্তে রয়েছে।

"আপনি যদি কঠোরতায় বিশ্বাস করেন, তবে আপনার বিশ্বাস করা উচিত যে কঠোরতা প্রমাণ করা কঠিন," কাবানেটস বলেছিলেন।

মেটাভার্সে

P ≠ NP অনুমানের প্রভাব এবং এটি প্রমাণ করার অসুবিধার মধ্যে সেই সংযোগটি ছিল কৌতুহলজনক, কিন্তু পিন করা কঠিন। একটি জিনিসের জন্য, প্রাকৃতিক প্রমাণের বাধা শুধুমাত্র P ≠ NP প্রমাণ করার একটি পদ্ধতিকে অবরুদ্ধ করে। অন্যটির জন্য, এটি P ≠ NP প্রমাণ করার অসুবিধাকে P ≠ NP এর সাথে নয়, কিন্তু সুরক্ষিত ক্রিপ্টোগ্রাফির অস্তিত্বের সাথে যুক্ত করেছে — একটি ঘনিষ্ঠভাবে সম্পর্কিত কিন্তু পুরোপুরি সমতুল্য নয়। সংযোগটি সত্যিই বুঝতে, গবেষকদের মেটা-জটিলতার সাথে স্বাচ্ছন্দ্য পেতে হবে।

"এই অন্তর্দৃষ্টি আছে যে 'ওহ, কারণ P ≠ NP, এটা প্রমাণ করা কঠিন যে P ≠ NP,'" উইলিয়ামস বলেছিলেন। "কিন্তু এমনকি এই অন্তর্দৃষ্টিকে উপলব্ধি করার জন্য, আপনাকে P ≠ NP-এর মতো কিছু একটি গণনাগত সমস্যা হিসাবে প্রমাণ করার কাজ সম্পর্কে চিন্তা করা শুরু করতে হবে।"

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

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

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

Kabanets এবং Cai-এর গবেষণাপত্রটি Razborov এবং Rudich-এর প্রাকৃতিক প্রমাণ বাধা গঠনের মধ্যে অন্তর্নিহিত একটি গণনাগত সমস্যা তুলে ধরে: একটি বুলিয়ান ফাংশনের সত্য সারণী দেওয়া, এটি উচ্চ বা নিম্ন সার্কিট জটিলতা আছে কিনা তা নির্ধারণ করুন। তারা এটিকে সর্বনিম্ন সার্কিট আকারের সমস্যা বা MCSP বলে অভিহিত করেছে।

MCSP হল একটি সর্বোত্তম মেটা-জটিলতা সমস্যা: একটি গণনাগত সমস্যা যার বিষয় গ্রাফ তত্ত্ব বা অন্য কোনো বাহ্যিক বিষয় নয়, বরং জটিলতা তত্ত্ব নিজেই। প্রকৃতপক্ষে, এটি প্রশ্নটির একটি পরিমাণগত সংস্করণের মতো যা 1980 এর দশকে সার্কিট জটিলতা পদ্ধতি ব্যবহার করে জটিলতা তাত্ত্বিকদের P বনাম NP মোকাবেলা করতে চালিত করেছিল: কোন বুলিয়ান ফাংশনগুলি গণনা করা কঠিন এবং কোনটি সহজ?

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

জটিলতা তাত্ত্বিকরা এই জাদুকরী অ্যালগরিদমটি তাদের কাজের বাইরে রেখে দেওয়ার বিষয়ে চিন্তা করেন না - তারা মনে করেন না এটি আদৌ বিদ্যমান, কারণ রাজবোরভ এবং রুডিচ দেখিয়েছেন যে নিম্ন-জটিলতার সত্য টেবিলগুলি থেকে উচ্চ-জটিলতার সত্য সারণীকে আলাদা করার জন্য এই জাতীয় যে কোনও অ্যালগরিদম ক্রিপ্টোগ্রাফি তৈরি করবে। অসম্ভব তার মানে MCSP সম্ভবত একটি হার্ড কম্পিউটেশনাল সমস্যা। কিন্তু এটা কতটা কঠিন? এটি কি এনপি-সম্পূর্ণ, যেমন হ্যামিল্টোনিয়ান পথ সমস্যা এবং প্রায় প্রতিটি অন্যান্য সমস্যা যা গবেষকরা 1960-এর দশকে লড়াই করেছিলেন?

NP-তে সমস্যার জন্য, "এটা কতটা কঠিন?" উত্তর দেওয়া সাধারণত যথেষ্ট সহজ, কিন্তু MCSP একটি অদ্ভুত আউটলায়ার বলে মনে হয়েছিল। "আমাদের খুব কম 'ভাসমান' সমস্যা রয়েছে যা এনপি-সম্পূর্ণ সমস্যার এই দ্বীপের সাথে সংযুক্ত করা হয়নি, যদিও সেগুলি কঠিন বলে মনে হয়," কাবানেতস বলেছিলেন।

Kabanets জানত যে তিনি এবং Cai প্রথম সমস্যাটি বিবেচনা করেননি যে তারা MCSP ডাব করেছিল। সোভিয়েত গণিতবিদরা 1950 এর দশকের শুরুতে একটি খুব অনুরূপ সমস্যা অধ্যয়ন করেছিলেন, বিভিন্ন গণনাগত সমস্যার অন্তর্নিহিত অসুবিধা বোঝার প্রাথমিক প্রচেষ্টায়। লিওনিড লেভিন 1960-এর দশকের শেষের দিকে NP-সম্পূর্ণতার তত্ত্ব তৈরি করার সময় এটির সাথে কুস্তি করেছিলেন, কিন্তু তিনি এটিকে NP-সম্পূর্ণ প্রমাণ করতে পারেননি, এবং তিনি এটি ছাড়াই তার মূল গবেষণাপত্র প্রকাশ করেছিলেন।

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

"এটি, এক অর্থে, মেটা-মেটা-জটিলতা," বলেছেন রাহুল সান্থানম, অক্সফোর্ড বিশ্ববিদ্যালয়ের জটিলতা তত্ত্ববিদ।

কিন্তু এটা কি কঠোরতা কম ছিল, নাকি অন্ততপক্ষে বোঝার কোনো উপায় ছিল কেন গবেষকরা প্রমাণ করতে সফল হননি যে এমসিএসপি এনপি-সম্পূর্ণ ছিল? Kabanets আবিষ্কার করেছেন যে, হ্যাঁ, একটি কারণ ছিল: সার্কিট জটিলতা বোঝার অসুবিধা এমসিএসপি-এর এনপি-সম্পূর্ণতা প্রমাণ করার জন্য যে কোনও পরিচিত কৌশলে বাধার মতো কাজ করে - একটি সমস্যা যা সার্কিট জটিলতা বোঝার অসুবিধা সম্পর্কে নিজেই। প্রাকৃতিক প্রমাণ বাধার বাঁকানো, আত্ম-পরাজিত যুক্তি অনিবার্য বলে মনে হয়েছিল।

এটাও সম্ভব যে MCSP NP-সম্পূর্ণ নয়, কিন্তু সেটাও অসম্ভাব্য বলে মনে হচ্ছে — সমস্যার কিছু সরল রূপ ইতিমধ্যেই NP-সম্পূর্ণ বলে পরিচিত।

ইম্পাগ্লিয়াজো বলেন, "আমাদের কাছে এটি রাখার জন্য একটি সুন্দর জায়গা নেই যা সরাসরি এটিকে অন্যান্য সমস্ত সমস্যার সাথে সম্পর্কিত করে যা আমরা অধ্যয়ন করি।"

কাবানেটস এমসিএসপির অদ্ভুত আচরণকে আলোকিত করেছিলেন, কিন্তু তিনি জানতেন না কীভাবে আরও অগ্রগতি করা যায়। মেটা-কমপ্লেক্সিটি রিসার্চের গতি কমে গেছে। এটি 16 বছর পরে আবার বিকাশ লাভ করবে, যখন গবেষকরা আরেকটি মৌলিক প্রশ্নের সাথে একটি আশ্চর্যজনক সংযোগ আবিষ্কার করেছিলেন: আপনি যদি বেশিরভাগ সময় সঠিক উত্তর পাওয়ার বিষয়ে চিন্তা করেন তবে সমস্যার সমাধান করা কতটা কঠিন?

বিশ্বের যুদ্ধ

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

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

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

এটি আসলে লেভিনই ছিলেন যিনি গড়-কেস জটিলতার কঠোর অধ্যয়নের সূচনা করেছিলেন, এনপি-সম্পূর্ণতার উপর তার অগ্রণী কাজের এক দশক পরে। মধ্যবর্তী বছরগুলিতে, তিনি সোভিয়েত কর্তৃপক্ষের বিরুদ্ধে ঝাঁপিয়ে পড়েছিলেন - তিনি ছিলেন একজন অযৌক্তিক সমস্যা সৃষ্টিকারী যিনি মাঝে মাঝে তার কমিউনিস্ট পার্টি যুবদলের দেশপ্রেমিক কার্যকলাপকে দুর্বল করে দিতেন। 1972 সালে, তিনি স্পষ্টভাবে রাজনৈতিক কারণে তার ডক্টরেট প্রত্যাখ্যান করেছিলেন।

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

লেভিন 1978 সালে মার্কিন যুক্তরাষ্ট্রে চলে আসেন এবং 1980-এর দশকের মাঝামাঝি সময়ে তিনি গড়-কেস জটিলতার দিকে মনোযোগ দেন। তিনি তৎকালীন স্নাতক ছাত্র ইমপাগ্লিয়াজো সহ তত্ত্বটি আরও বিকাশের জন্য অন্যদের সাথে কাজ শুরু করেছিলেন। কিন্তু তাদের অগ্রগতি হলেও, ইম্পাগ্লিয়াজো দেখতে পান যে গবেষকরা প্রায়ই একে অপরের অতীত কথা বলে। তিনি সবাইকে একই পৃষ্ঠায় আনতে চেয়েছিলেন, এবং এটি সাহায্য করেনি যে লেভিনের কাগজপত্রগুলি বিখ্যাতভাবে সংক্ষিপ্ত ছিল - যেটি ক্ষেত্র শুরু করেছে গড় কেস জটিলতা দুই পৃষ্ঠারও কম দীর্ঘ ছিল।

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

সার্জারির কাগজ, 1995 সালে প্রকাশিত, একটি তাত্ক্ষণিক ক্লাসিক হয়ে ওঠে। ইম্পাগ্লিয়াজোর জন্য উদ্ভট নাম তৈরি করেছে পাঁচটি বিশ্ব কম্পিউটেশনাল কঠোরতা এবং বিভিন্ন ক্রিপ্টোগ্রাফিক ক্ষমতার বিভিন্ন ডিগ্রি দ্বারা আলাদা। আমরা এই জগতের একটিতে বাস করি, কিন্তু কোনটি আমরা জানি না।

ইমপাগ্লিয়াজোর গবেষণাপত্রটি প্রকাশিত হওয়ার পর থেকে, গবেষকরা তার ক্ষুদ্রাকৃতি মাল্টিভার্সের অংশগুলিকে নির্মূল করার স্বপ্ন দেখেছেন - কিছু কিছু বিশ্ব সম্ভব নয় বলে প্রমাণ করে সম্ভাবনার স্থানকে সংকুচিত করে৷ দুটি বিশ্ব বিশেষভাবে প্রলোভনসঙ্কুল লক্ষ্য: যেখানে ক্রিপ্টোগ্রাফি অসম্ভব যদিও P ≠ NP।

হিউরিস্টিকা নামে পরিচিত এই জগতের একটিতে, সমস্ত এনপি-সম্পূর্ণ সমস্যাগুলি বেশিরভাগ ইনপুটগুলিতে সমাধান করা সহজ, তবে দ্রুত অ্যালগরিদমগুলি মাঝে মাঝে ভুল করে, তাই এই সমস্যাগুলি এখনও সবচেয়ে খারাপ-কেস জটিলতা তত্ত্বের মান দ্বারা কঠিন বলে বিবেচিত হয়। এটি এমন একটি বিশ্ব যেখানে ক্রিপ্টোগ্রাফি অসম্ভব কারণ প্রায় প্রতিটি কোড সহজেই ক্র্যাক হয়ে যায়। পেসিল্যান্ড নামে পরিচিত অন্য বিশ্বে, ক্রিপ্টোগ্রাফি একটি ভিন্ন কারণে অসম্ভব: প্রতিটি সমস্যা গড়-কেস অর্থে কঠিন, কিন্তু একটি বার্তা এনক্রিপ্ট করা এটিকে উদ্দেশ্যপ্রণোদিত প্রাপকের জন্যও অযোগ্য করে তোলে।

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

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

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

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

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

কারমোসিনো বলেন, "আমি সেই সময় সেই কাগজের প্রতি আচ্ছন্ন ছিলাম।" "কিছুই পরিবর্তিত হয়েছে."

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

"তিনি একটি ভাল উপায়ে লোকেদের বাগড়াচ্ছিলেন," কাবানেটস স্মরণ করেন।

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

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

"এটা স্পষ্ট ছিল না যে এই জাতীয় সংযোগটি আদৌ বিদ্যমান থাকবে," ইম্পাগ্লিয়াজো বলেছিলেন।

MCSP-এর জন্য একটি দ্রুত অ্যালগরিদম সাধারণ বুলিয়ান সার্কিটগুলির জন্য সম্পূর্ণরূপে অনুমানমূলক: এর বিপরীতে সমস্ত প্রমাণ থাকা সত্ত্বেও MCSP একটি সহজ কম্পিউটেশনাল সমস্যা হিসাবে পরিণত না হওয়া পর্যন্ত এটি বিদ্যমান থাকতে পারে না এবং এর অর্থ হল চার গবেষকের গবেষণাপত্র দ্বারা উহ্য শেখার অ্যালগরিদম সমানভাবে অনুমানমূলক।

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

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

ফলাফল অন্যান্য বিষয়ে কাজ করা জটিলতা তত্ত্ববিদদের মনোযোগ আকর্ষণ করে। এটি মেটা-জটিলতা এবং গড়-কেস জটিলতার মধ্যে আরও সংযোগের একটি পূর্বরূপ ছিল যা আগামী বছরগুলিতে আবির্ভূত হবে।

সর্বোপরি, এটি একটি প্রমাণ ছিল যে গবেষকরা বাধাগুলি সম্পর্কে সহজ প্রশ্ন জিজ্ঞাসা করে কতদূর যেতে পারেন যা প্রথমে তাদের অগ্রগতিতে বাধা দেয় বলে মনে হয়।

"এই ধরনের দ্বৈততা অন্তত গত 30 বা 40 বছরের জটিলতা জুড়ে একটি থিম," ইম্পাগ্লিয়াজো বলেছেন। "বাধা প্রায়ই সুযোগ।"

আংশিক কৃতিত্ব

কার্মোসিনো এবং তার সহকর্মীরা তাদের গবেষণাপত্র প্রকাশ করার পর থেকে কয়েক বছরেই অগ্রগতি ত্বরান্বিত হয়েছে।

"নতুন জিনিস ঘটছে," কোলোকোলোভা বলেছেন। "অনেক সত্যিই, সত্যিই উজ্জ্বল জুনিয়র গবেষক আছেন।"

ইলাঙ্গো এই তরুণ গবেষকদের একজন — স্নাতক স্কুলের তার প্রথম তিন বছরে, তিনি একটি দ্বি-মুখী কৌশল ব্যবহার করে MCSP NP-সম্পূর্ণ প্রমাণ করার ভয়ঙ্কর উন্মুক্ত সমস্যাকে আক্রমণ করেছেন: NP-সম্পূর্ণতা প্রমাণ করা সহজ সংস্করণ MCSP-এর, যেমন সার্কিট জটিলতা গবেষকরা 1980-এর দশকে P বনাম NP আক্রমণ করার সময় করেছিলেন, পাশাপাশি NP- সম্পূর্ণতা প্রমাণ করেছিলেন আরো জটিল সংস্করণ, যা স্বজ্ঞাতভাবে কঠিন বলে মনে হয় এবং এইভাবে কঠিন প্রমাণ করা সম্ভবত সহজ।

ইলাঙ্গো মেটা-জটিলতার প্রতি তার আগ্রহের কৃতিত্ব দেয় এরিক অ্যালেন্ডার, Rutgers বিশ্ববিদ্যালয়ের একজন জটিলতা তত্ত্ববিদ এবং কয়েকজন গবেষক যারা 2000 এবং 2010 এর দশকের শুরুতে মেটা-জটিলতার উপর কাজ চালিয়ে গেছেন তাদের একজন। "তার উত্সাহ সংক্রামক ছিল," ইলাঙ্গো বলেছিলেন।

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

হিরাহারের ফলাফল উত্তেজনাপূর্ণ কারণ অনেক গবেষক সন্দেহ করেন যে MCSP NP-সম্পূর্ণ, অন্যান্য সমস্ত সমস্যার বিপরীতে যার জন্য সবচেয়ে খারাপ-কেস থেকে গড়-কেস হ্রাস জানা যায়। যদি তারা সমস্ত গড়-কেস অ্যালগরিদমগুলি কভার করার জন্য হিরাহারের ফলাফলগুলিকে প্রসারিত করতে পারে এবং তারপরে প্রমাণ করে যে MCSP NP-সম্পূর্ণ, তাহলে এটি প্রমাণ করবে যে আমরা হিউরিস্টিকায় বাস করি না।

"এটি সত্যিই একটি পৃথিবী বিধ্বংসী ফলাফল হবে," Santhanam বলেন.

MCSP যে NP-সম্পূর্ণ তা প্রমাণ করা একটি লম্বা আদেশের মতো মনে হতে পারে — সর্বোপরি, প্রশ্নটি 50 বছরেরও বেশি সময় ধরে খোলা আছে। কিন্তু পরে ক শত্রুবূহ্যভেদ গত বছর Hirahara দ্বারা, গবেষকরা এখন অনেক কাছাকাছি যে কেউ কয়েক বছর আগে আশা করা হবে.

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

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

এই ফলাফলটি হিরাহারের আগের কাজের তুলনায় মেটা-জটিলতায় গবেষকদের আরও বেশি উত্সাহিত করেছিল এবং অন্যান্য গবেষকরাও লক্ষ্য করেছিলেন — জটিলতা তত্ত্ববিদ এবং ব্লগার ল্যান্স ফোর্টনো এটিকে ডাব করেছেন বছরের ফলাফল. কারণ কম্পিউটেশনাল সমস্যার এই ধরনের "আংশিক ফাংশন" সংস্করণগুলিকে মোকাবেলা করা অন্যান্য এনপি-সম্পূর্ণতা প্রমাণগুলির মধ্যে একটি গুরুত্বপূর্ণ মধ্যবর্তী পদক্ষেপ।

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

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

অনুপস্থিত টুকরা

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

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

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

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

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

পি বনাম এনপি প্রশ্নের উত্তর দেওয়ার জন্য গবেষকরা তাদের সংগ্রাম থেকে যদি একটি পাঠ শিখে থাকেন — বা এমনকি শুধু বুঝতে পারেন — তাহলে জটিলতা তত্ত্ব নিজেই জটিল। কিন্তু সেই চ্যালেঞ্জটিই যা অনুসন্ধানটিকে এত ফলপ্রসূ করে তোলে।

কারমোসিনো বলেছেন, "এটি আসলেই এক ধরণের দুর্দান্ত যে এটি এত কঠিন।" "আমি কখনই বিরক্ত হব না।"

সম্পাদকের নোট: স্কট অ্যারনসন এর সদস্য Quanta ম্যাগাজিন'গুলি উপদেষ্টা পর্ষদ.