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

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

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

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

"তারা সত্যিই সুন্দর এবং গুরুত্বপূর্ণ ফলাফল," বলেন এরিক অ্যালেন্ডার, রাটগার্স বিশ্ববিদ্যালয়ের একজন তাত্ত্বিক কম্পিউটার বিজ্ঞানী।

কঠোরতা সংজ্ঞায়িত করা

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

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

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

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

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

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

ওয়ান-ওয়ে ট্রাফিক

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

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

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

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

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

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

ডেটা স্ট্রাকচারের উপর বিল্ডিং

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

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

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

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

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

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

ইউনিফর্মের বাইরে

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

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

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

Fiat-Naor অ্যালগরিদম দ্বারা ব্যবহৃত ডেটা স্ট্রাকচার সবসময় একটি নির্দিষ্ট ফাংশনের জন্য তৈরি করা হয়। একটি 10-বিট স্ট্রিং স্ক্র্যাম্বল করে এমন একটি ফাংশন উল্টাতে, আপনার একটি ডেটা স্ট্রাকচার প্রয়োজন যা আপনাকে একটি ফাংশন উল্টাতে হবে যা একটি 20-বিট স্ট্রিং স্ক্র্যাম্বল করে, এমনকি যদি স্ক্র্যাম্বলিং একইভাবে করা হয়। এটি ফিয়াট-নাওরকে একটি ননইনিফর্ম অ্যালগরিদম করে তোলে।

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

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

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

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

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

ইনভার্সন কনভারজেন্স

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

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

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

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

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

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