লঘুকরণযোগ্যতা এবং অদ্রবণীয়তার মাত্রা

লঘুকরণযোগ্যতা একটি সমস্যাকে অন্যটিতে রূপান্তরিত করে সমস্যাগুলির জটিলতার তুলনা করে, এবং সমান জটিলতার সমস্যাগুলিকে একত্রিত করে অদ্রবণীয়তার মাত্রা তৈরি করে যা গণনযোগ্যতার বাইরের বিশ্বকে কাঠামোবদ্ধ করে।

Definition

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

Scope

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

Core questions

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

Key theories

লঘুকরণযোগ্যতা এবং টুরিং জাম্প

টুরিং লঘুকরণযোগ্যতা ওরাকল গণনার মাধ্যমে সমস্যাগুলিকে সম্পর্কিত করে, এবং একটি সমস্যার জাম্প, এর সাপেক্ষে থামার এনকোডিং, সর্বদা কঠোরভাবে আরও কঠিন, যা কঠিন থেকে কঠিনতর সমস্যার একটি অন্তহীন টাওয়ার তৈরি করে।

মধ্যবর্তী মাত্রার অস্তিত্ব

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

Clinical relevance

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

History

টুরিং ১৯৩৯ সালে ওরাকল মেশিন প্রবর্তন করেন, এবং পোস্ট ১৯৪৪ সালে অদ্রবণীয়তার মাত্রাগুলির অধ্যয়নকে কাঠামোবদ্ধ করেন এবং মধ্যবর্তী গণনাযোগ্যভাবে গণনযোগ্য মাত্রার অস্তিত্ব আছে কিনা তা নিয়ে প্রশ্ন তোলেন। ফ্রাইডবার্গ এবং মুচনিক ১৯৫৬-১৯৫৭ সালে স্বাধীনভাবে অগ্রাধিকার পদ্ধতি আবিষ্কার করে এটি সমাধান করেন, যা বিষয়টির একটি কেন্দ্রীয় কৌশল হয়ে ওঠে।

Key figures

• Emil Post
• Alan Turing
• Richard Friedberg
• Albert Muchnik

Seminal works

• soare2016
• rogers1987

Frequently asked questions

একটি লঘুকরণ কী, স্বজ্ঞাতভাবে?

এটি অন্যটির জন্য একটি সমাধানকারী ব্যবহার করে একটি সমস্যা সমাধানের একটি উপায়। যদি আপনি সমস্যা A-এর যেকোনো দৃষ্টান্তকে সমস্যা B-এর একটি দৃষ্টান্তে অনুবাদ করতে পারেন যাতে উত্তরগুলি মিলে যায়, তবে B অন্তত A-এর মতো কঠিন, এবং B-এর একটি সমাধান A-এর একটি সমাধান প্রদান করে।

থামার সমস্যার চেয়ে কঠিন সমস্যা আছে কি?

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