কম্পিউটার বিজ্ঞানীরা প্রধান অ্যালগরিদমিক লক্ষ্যের কাছাকাছি ইঞ্চি | কোয়ান্টা ম্যাগাজিন

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

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

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

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

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

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

তুলনা তুলনা

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

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

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

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

দুটি গ্রুপ আইসোমরফিক হয় যদি আপনি একটি গ্রুপের প্রতিটি উপাদানকে অন্যটিতে একটি উপাদানের সাথে যুক্ত করতে পারেন, যাতে প্রথম গ্রুপের দুটি উপাদানের উপর কাজ করার ফলাফল দ্বিতীয়টিতে ঐ উপাদানগুলির সমতুল্য মানের উপর কাজ করার ফলাফলের সাথে সামঞ্জস্যপূর্ণ হয়। দল

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

গ্রুপগুলো আইসোমরফিক কারণ এর সাথে 0 জোড়া a, 1 জোড়া সঙ্গে b, এবং উপাদান একত্রিত করে উত্পাদিত কাঠামোগত সম্পর্ক উভয় গ্রুপে একই।

"আমরা বলি যে দুটি গ্রুপ আইসোমরফিক হয় যদি তারা মূলত সমতুল্য হয়," সান বলেছিলেন।

ভারসাম্যহীন অগ্রগতি

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

যে পরিমাপ চতুর হতে পারে. একটি অ্যালগরিদমের গতির উপর ভিত্তি করে এটি কাজ করছে বস্তুর আকারের সাথে তার রানটাইম কিভাবে পরিবর্তিত হয়। উদাহরণস্বরূপ, কল্পনা করুন যে আপনার দুটি জোড়া গ্রুপ রয়েছে। এক জোড়ায়, প্রতিটি গ্রুপে পাঁচটি উপাদান রয়েছে। অন্যটিতে, প্রতিটি গ্রুপে 10টি উপাদান রয়েছে।

আপনি আশা করবেন যে আরও উপাদান সহ গ্রুপগুলি আইসোমরফিক কিনা তা নির্ধারণ করতে এটি একটি অ্যালগরিদম আরও সময় নেবে। কিন্তু আর কত সময়? এটা কি দ্বিগুণ সময় লাগবে? 5² দীর্ঘ? 2⁵ দীর্ঘ? এই প্রশ্নগুলি অ্যালগরিদমিক গতির গুরুত্বপূর্ণ বিস্তৃত শ্রেণীবিভাগের সাথে মিলে যায়: তারা রৈখিক সময়ে চলতে পারে (যার অর্থ এই ক্ষেত্রে এটি দ্বিগুণ সময় নেয়), বহুপদী সময় (5² দীর্ঘ) এবং সূচকীয় সময় (2⁵ দীর্ঘ)।

কম্পিউটার বিজ্ঞানীরা জানেন যে কোন গতি বিভাগে সর্বাধিক কম্পিউটিং প্রশ্নগুলি পড়ে, তবে সবগুলি নয়।

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

1970s মধ্যে, রবার্ট টারজান প্রিন্সটন ইউনিভার্সিটি বুঝতে পেরেছে যে একটি অ্যালগরিদম আছে যা নির্ধারণ করতে পারে যে কোন দুটি গ্রুপ আইসোমরফিক কিনা $latex n^{{(log,n)}}$ এর রানটাইম দিয়ে, যেখানে n প্রতিটি গ্রুপে উপাদানের সংখ্যা। একে বলা হয় একটি আধা-পলিনোমিয়াল-টাইম অ্যালগরিদম, এবং রানটাইমের অনুক্রমে এটি সূচকীয় সময়ের চেয়ে ভাল (2ⁿ) কিন্তু বহুপদী সময়ের চেয়েও খারাপ (n²) এটি প্রায় বাবাইয়ের গ্রাফ আইসোমরফিজম অ্যালগরিদমের মতো একই গতি, এবং এটি এখনও প্রায় 50 বছর পরে গোষ্ঠীগুলির জন্য আমরা করতে পারি সেরা।

"এর মোটামুটি অর্থ হল অর্ধ শতাব্দী ধরে কোনও অগ্রগতি হয়নি," সান বলেছিলেন।

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

"আমাদের সমস্ত সরঞ্জামগুলি বছরের পর বছর ধরে সত্যিই ধীরগতির ছিল, এবং বীজগণিত [গোষ্ঠীর]] সম্পর্কে আমরা যা জানি তা কাজে লাগানো কঠিন," বলেছেন জেমস উইলসন কলোরাডো স্টেট ইউনিভার্সিটির।

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

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

একটি সমস্যা রূপান্তরিত

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

সূর্যের কাজটিতে কয়েকটি ধারণা রয়েছে যা একটি গুরুত্বপূর্ণ ধরণের গোষ্ঠীকে লক্ষ্য করে এবং তাদের তুলনা করার জন্য সেই দলগুলিকে টুকরো টুকরো করার জন্য একটি চতুর উপায় খুঁজে বের করে।

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

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

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

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

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

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

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

সূর্যের অগ্রগতি দেখাচ্ছিল যে ম্যাট্রিক্স স্পেসগুলির জন্য এই বিভাজন করা সর্বদা সম্ভব pক্লাস 2 এবং সূচকের গ্রুপ p. তারপর তিনি প্রমাণ করেছিলেন যে এই ধরনের বিভাজনের পরে, অ্যালগরিদমিক কৌশলগুলির সংমিশ্রণ এটি নির্ধারণ করা সম্ভব করে যে দুটি স্পেস আইসোমরফিক কিনা $latex n^{{(log,n)}^{5/6}}$ সময়ে, একটি মান যা Tarjan এর $latex n^{{(log,n)}}$ পদ্ধতির চেয়ে সামান্য কম। (উভয় অ্যালগরিদমে ধ্রুবক পদগুলিও অন্তর্ভুক্ত থাকে, যা রানটাইমে বড় প্রভাব ফেলে না এবং যা আমরা স্পষ্টতার জন্য ছেড়ে দিয়েছি।)

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

“যদি আপনি এটি সমাধান করতে পারেন p-গোষ্ঠী, সম্ভবত আপনি পুরো জিনিসটি সমাধান করতে পারেন, "গ্রোচো বলেছিলেন। "হতে পারে."