Random self-reducibility
র্যান্ডম সেলফ-রিডিউসিবিলিটি (আরএসআর) হল একটি নিয়ম যে গড় ক্ষেত্রে একটি ভাল অ্যালগরিদম সবচেয়ে খারাপ ক্ষেত্রে একটি ভাল অ্যালগরিদম বোঝায়। আরএসআর হল দৃষ্টান্তের একটি বড় অংশ সমাধান করে একটি সমস্যার সমস্ত দৃষ্টান্ত সমাধান করার ক্ষমতা। সংজ্ঞা যদি কোনও ফাংশন f-এর জন্য যে কোনও দৃষ্টান্ত x-এর মূল্যায়ন বহুপদী সময়ে এক বা একাধিক এলোমেলো দৃষ্টান্ত yi-তে f-এর মূল্যায়নে হ্রাস করা যায়, তবে এটি স্ব-হ্রাসযোগ্য (এটি একটি অ-অভিযোজিত অভিন্ন স্ব-হ্রাস হিসাবেও পরিচিত)। একটি এলোমেলো স্ব-হ্রাসে, f-এর ডোমেনে একটি নির্বিচারে সবচেয়ে খারাপ-কেস দৃষ্টান্ত x-কে y1,., yk দৃষ্টান্তের একটি এলোমেলো সেটের সাথে ম্যাপ করা হয়। এটি করা হয় যাতে f (x) বহুপদী সময়ে গণনা করা যায়, ম্যাপিং থেকে মুদ্রা-টস ক্রম দেওয়া, x, এবং f (y1),., f (yk)। অতএব, yi-এর উপর প্রবর্তিত বন্টনের সাপেক্ষে গড় গ্রহণ করলে, f-এর গড়-কেস জটিলতা f-এর সবচেয়ে খারাপ-কেস র্যান্ডমাইজড জটিলতা হিসাবে একই (বহুপদী কারণগুলির মধ্যে)। একটি বিশেষ ক্ষেত্রে লক্ষণীয় হল যখন প্রতিটি র্যান্ডম দৃষ্টান্ত yi f-এর ডোমেনের উপাদানগুলির পুরো সেটের উপর অভিন্নভাবে বিতরণ করা হয় যার দৈর্ঘ্য |x।।। এই ক্ষেত্রে f গড় হিসাবে ততটাই কঠিন যতটা এটি সবচেয়ে খারাপ ক্ষেত্রে হয়। এই পদ্ধতিতে দুটি প্রধান সীমাবদ্ধতা রয়েছে। প্রথমে y1,., yk-এর প্রজন্মটি অ-অভিযোজিতভাবে সঞ্চালিত হয়। এর অর্থ হল f (y1) জানার আগেই y2 বাছাই করা হয়। দ্বিতীয়ত, y1,., yk পয়েন্টগুলি সমানভাবে বিতরণ করার প্রয়োজন নেই। ক্রিপ্টোগ্রাফিক প্রোটোকলগুলিতে প্রয়োগ এমন সমস্যা যা ডেটাতে কিছু গোপনীয়তার প্রয়োজন হয় (সাধারণত ক্রিপ্টোগ্রাফিক সমস্যা) সেই গোপনীয়তা নিশ্চিত করতে র্যান্ডমাইজেশন ব্যবহার করতে পারে। প্রকৃতপক্ষে, একমাত্র প্রমাণযোগ্যভাবে সুরক্ষিত ক্রিপ্টোগ্রাফিক সিস্টেমের (ওয়ান-টাইম প্যাড) নিরাপত্তা সম্পূর্ণরূপে সিস্টেমে সরবরাহ করা মূল তথ্যের এলোমেলোতার উপর নির্ভর করে। ক্রিপ্টোগ্রাফির ক্ষেত্রটি এই সত্যটি ব্যবহার করে যে নির্দিষ্ট সংখ্যা-তাত্ত্বিক ফাংশনগুলি এলোমেলোভাবে স্ব-হ্রাসযোগ্য। এর মধ্যে রয়েছে সম্ভাব্য এনক্রিপশন এবং ক্রিপ্টোগ্রাফিকভাবে শক্তিশালী সিউডোরান্ডম নম্বর জেনারেশন। এছাড়াও, ইনস্ট্যান্স-হাইডিং স্কিমগুলি (যেখানে একটি দুর্বল ব্যক্তিগত ডিভাইস তার ডেটা প্রকাশ না করে একটি শক্তিশালী পাবলিক ডিভাইস ব্যবহার করে) সহজেই এলোমেলো স্ব-হ্রাস দ্বারা উদাহরণস্বরূপ দেওয়া হয়। উদাহরণস্বরূপ, বিচ্ছিন্ন লগারিদম সমস্যা, দ্বিঘাত অবশিষ্টাংশ সমস্যা, আরএসএ বিপরীত সমস্যা এবং একটি ম্যাট্রিক্সের স্থায়ী গণনা করার সমস্যা হল প্রতিটি এলোমেলো স্ব-হ্রাসযোগ্য সমস্যা। বিচ্ছিন্ন লগারিদম উপপাদ্যঃ |G। আকারের একটি চক্রাকার গ্রুপ G দেওয়া হয়েছে। যদি একটি নির্ধারক বহুপদী সময় অ্যালগরিদম এ সমস্ত ইনপুটের 1/পলি (এন) ভগ্নাংশের জন্য পৃথক লগারিদম গণনা করে (যেখানে এন = লগ |G। হল ইনপুট আকার), তবে সমস্ত ইনপুটের জন্য পৃথক লগারিদমের জন্য একটি র্যান্ডমাইজড বহুপদী সময় অ্যালগরিদম রয়েছে। একটি চক্রাকার গোষ্ঠী জি = {জিআই। 0 ≤ আই <|G।}-এর একটি জেনারেটর জি এবং একটি এক্স ω জি দেওয়া হলে, বেস জি-তে এক্স-এর বিচ্ছিন্ন লগ হল x = জিকে সহ পূর্ণসংখ্যা কে (0 ≤ কে <|G।)। B-কে {0,., |G। −1}-এ সমানভাবে বিতরণ করার জন্য নিন, তারপর xgB = gk + B-ও G-তে সমানভাবে বিতরণ করা হয়। অতএব xgB x থেকে স্বাধীন, এবং এর লগারিদম বহুপদী সময়ে সম্ভাব্যতা 1/বহু (n) দিয়ে গণনা করা যেতে পারে। তারপর loggx ষ্ণ loggxgB-B (মোড |G।) এবং বিচ্ছিন্ন লগারিদম স্ব-হ্রাসযোগ্য। একটি ম্যাট্রিক্সের স্থায়ী একটি ম্যাট্রিক্সের স্থায়ী সংজ্ঞার পরিপ্রেক্ষিতে, এটি স্পষ্ট যে যে কোনও এন-বাই-এন ম্যাট্রিক্স এম-এর জন্য পিইআরএম (এম) হল এম-এর এন্ট্রিগুলির উপর ডিগ্রি এন-এর একটি মাল্টিভ্যারিয়েট পলিনোমিয়াল। একটি ম্যাট্রিক্সের স্থায়ী গণনা করা একটি কঠিন গণনামূলক কাজ-পিইআরএমকে #P-সম্পূর্ণ (প্রমাণ) হিসাবে দেখানো হয়েছে। উপরন্তু, বেশিরভাগ ম্যাট্রিক্সের জন্য পিইআরএম (এম) গণনা করার ক্ষমতা একটি এলোমেলো প্রোগ্রামের অস্তিত্বকে বোঝায় যা সমস্ত ম্যাট্রিক্সের জন্য পিইআরএম (এম) গণনা করে। এটি দেখায় যে PERM এলোমেলোভাবে স্ব-হ্রাসযোগ্য। নীচের আলোচনাটি সেই ক্ষেত্রে বিবেচনা করে যেখানে ম্যাট্রিক্স এন্ট্রিগুলি কিছু মৌলিক p-এর জন্য একটি সীমাবদ্ধ ক্ষেত্র Fp থেকে টানা হয় এবং যেখানে সমস্ত পাটিগণিত সেই ক্ষেত্রে সঞ্চালিত হয়। ধরা যাক এক্স এফপি থেকে এন্ট্রি সহ একটি এলোমেলো এন-বাই-এন ম্যাট্রিক্স। যেহেতু যে কোনও ম্যাট্রিক্স M + kX-এর সমস্ত এন্ট্রি k-এর রৈখিক ফাংশন, সেই রৈখিক ফাংশনগুলিকে ডিগ্রি n মাল্টিভ্যারিয়েট পলিনোমিয়াল দিয়ে রচনা করে যা PERM (M) গণনা করে আমরা k-এর উপর আরেকটি ডিগ্রি n পলিনোমিয়াল পাই, যাকে আমরা p (k) বলব। স্পষ্টতই, পি (0) এম-এর স্থায়ী সমান। ধরুন আমরা এমন একটি প্রোগ্রাম জানি যা বেশিরভাগ এন-বাই-এন ম্যাট্রিক্সের জন্য পিইআরএম (এ)-এর সঠিক মান গণনা করে যার মধ্যে এফপি-------------------------------------------------------------------------------------------------------------------------------------------------------- তারপর প্রায় দুই-তৃতীয়াংশ সম্ভাব্যতা সহ, আমরা k = 1,2,., n + 1 এর জন্য PERM (M + kX) গণনা করতে পারি। একবার আমাদের সেই n + 1 মানগুলি হয়ে গেলে, আমরা ইন্টারপোলেশন ব্যবহার করে p (k) এর সহগের জন্য সমাধান করতে পারি (মনে রাখবেন যে p (k) এর ডিগ্রি n রয়েছে)। একবার আমরা p (k) সঠিকভাবে জানতে পারলে, আমরা p (0) মূল্যায়ন করি, যা PERM (M) এর সমান। যদি আমরা তা করি, তাহলে আমরা এক-তৃতীয়াংশ সময় ভুল হওয়ার ঝুঁকি নিয়ে চলি, কিন্তু একাধিক র্যান্ডম এক্স বাছাই করে এবং উপরের পদ্ধতিটি বহুবার পুনরাবৃত্তি করে, এবং শুধুমাত্র সংখ্যাগরিষ্ঠ বিজয়ীকে উত্তর হিসাবে প্রদান করে, আমরা ত্রুটির হারকে খুব কম করতে পারি। পরিণতি যদি একটি এন. পি-সম্পূর্ণ সমস্যা অ-অভিযোজিতভাবে এলোমেলোভাবে স্ব-হ্রাসযোগ্য হয় তবে বহুপদী শ্রেণিবিন্যাস σ3-এ ভেঙে যায়। যদি কোনও সি. ও. এন. পি-হার্ড সমস্যা ও-তে (লগ এন/এন) এলোমেলোভাবে স্ব-হ্রাসযোগ্য হয় তবে σ2 = Π2। রেফারেন্স এম. আবাদি, জে. ফাইগেনবাম এবং জে. কিলিয়ান, অন হাইডিং ইনফরমেশন ফ্রম অ্যান ওরাকল, জে. কম্পিউট। সিস্ট। বিজ্ঞান., 1989 এস. অরোরা, অ্যারাউন্ড দ্য পিসিপি থিওরেম, 1996 জে. ফাইগেনবাম, এল. ফোর্টনো, অন দ্য র্যান্ডম-সেলফ-রিডিউসিবিলিটি অফ কমপ্লিট সেটস, 1991 র্যান্ডমাইজড অ্যালগরিদম