Random self-reducibility
சீரற்ற சுய-குறைப்பு (ஆர். எஸ். ஆர்) என்பது சராசரி வழக்குக்கான ஒரு நல்ல வழிமுறை மோசமான நிகழ்வுக்கு ஒரு நல்ல வழிமுறை என்பதைக் குறிக்கிறது. ஆர்எஸ்ஆர் என்பது ஒரு சிக்கலின் அனைத்து நிகழ்வுகளையும் ஒரு பெரிய பகுதியைத் தீர்ப்பதன் மூலம் தீர்க்கும் திறன் ஆகும். வரையறை எந்தவொரு நிகழ்வையும் மதிப்பிடும் ஒரு செயல்பாட்டிற்கு x ஐ பல்லுறுப்புக்கோவை நேரத்தில் ஒன்று அல்லது அதற்கு மேற்பட்ட சீரற்ற நிகழ்வுகளில் yi இல் f இன் மதிப்பீட்டிற்கு குறைக்க முடியும் என்றால், அது சுய-குறைப்பு (இது தழுவல் அல்லாத சீரான சுய-குறைப்பு என்றும் அழைக்கப்படுகிறது). ஒரு சீரற்ற சுய-குறைப்பில், f இன் களத்தில் ஒரு தன்னிச்சையான மோசமான-வழக்கு நிகழ்வு x சீரற்ற நிகழ்வுகளின் தொகுப்பான y1,., yk க்கு வரைபடமாக்கப்படுகிறது. இது செய்யப்படுகிறது, இதனால் f (x) ஐ பல்லுறுப்புக்கோவை நேரத்தில் கணக்கிட முடியும், இது வரைபடத்திலிருந்து நாணயம்-டாஸ் வரிசையைக் கொடுக்கிறது, x, மற்றும் f (y1),., f (yk). எனவே, yi இல் தூண்டப்பட்ட விநியோகத்தைப் பொறுத்தவரை சராசரியை எடுத்துக் கொண்டால், f இன் சராசரி-வழக்கு சிக்கலானது (பல்லுறுப்புக்கோவை காரணிகளுக்குள்) f இன் மோசமான-வழக்கு சீரற்ற சிக்கலானது. ஒவ்வொரு சீரற்ற நிகழ்வும் yi |x | நீளம் கொண்ட f இன் களத்தில் உள்ள உறுப்புகளின் முழு தொகுப்பிலும் ஒரே மாதிரியாக விநியோகிக்கப்படும் போது ஒரு சிறப்பு நிகழ்வு குறிப்பிடத்தக்கது. இந்த விஷயத்தில் f சராசரியாக மிகவும் மோசமான நிலையில் இருப்பதைப் போலவே கடினமானது. இந்த அணுகுமுறை இரண்டு முக்கிய கட்டுப்பாடுகளைக் கொண்டுள்ளது. முதலில் y1,., yk இன் தலைமுறை தழுவல் இல்லாமல் செய்யப்படுகிறது. இதன் பொருள் f (y1) அறியப்படுவதற்கு முன்பு y2 தேர்ந்தெடுக்கப்படுகிறது. இரண்டாவதாக, y1,., yk புள்ளிகள் ஒரே மாதிரியாக விநியோகிக்கப்பட வேண்டிய அவசியமில்லை. குறியாக்க நெறிமுறைகளில் பயன்பாடு தரவுகளில் சில தனியுரிமை தேவைப்படும் சிக்கல்கள் (பொதுவாக குறியாக்க சிக்கல்கள்) அந்த தனியுரிமையை உறுதிப்படுத்த சீரற்றமயமாக்கலைப் பயன்படுத்தலாம். உண்மையில், ஒரே நிரூபிக்கக்கூடிய பாதுகாப்பான கிரிப்டோகிராஃபிக் அமைப்பு (ஒரு முறை பேட்) அதன் பாதுகாப்பைக் கொண்டுள்ளது, இது கணினிக்கு வழங்கப்பட்ட முக்கிய தரவுகளின் சீரற்ற தன்மையை முற்றிலும் நம்பியுள்ளது. குறியாக்கவியல் துறை சில எண்-கோட்பாட்டு செயல்பாடுகள் தோராயமாக சுய-குறைக்கப்படக்கூடியவை என்ற உண்மையைப் பயன்படுத்துகிறது. இதில் நிகழ்தகவு குறியாக்கம் மற்றும் குறியாக்கவியல் ரீதியாக வலுவான போலி எண் உருவாக்கம் ஆகியவை அடங்கும். மேலும், எடுத்துக்காட்டு-மறைக்கும் திட்டங்கள் (ஒரு பலவீனமான தனியார் சாதனம் அதன் தரவை வெளிப்படுத்தாமல் ஒரு வலுவான பொது சாதனத்தைப் பயன்படுத்துகிறது) சீரற்ற சுய குறைப்புகளால் எளிதில் எடுத்துக்காட்டப்படுகின்றன. தனித்த மடக்கை சிக்கல், இருபடி எஞ்சிய சிக்கல், ஆர்எஸ்ஏ தலைகீழ் சிக்கல் மற்றும் ஒரு மேட்ரிக்ஸின் நிரந்தரத்தை கணக்கிடுவதில் உள்ள சிக்கல் ஆகியவை ஒவ்வொன்றும் சீரற்ற சுய-குறைப்பு சிக்கல்களாகும். தனித்த மடக்கை தேற்றம்-|G | அளவு கொண்ட ஒரு சுழற்சி குழு G கொடுக்கப்பட்டுள்ளது. ஒரு தீர்மானகரமான பல்லுறுப்புக்கோவை நேர வழிமுறை A அனைத்து உள்ளீடுகளின் 1/பாலி (n) பின்னத்திற்கான தனித்த மடக்கைக் கணக்கிட்டால் (இங்கு n = log |G | என்பது உள்ளீட்டு அளவு), பின்னர் அனைத்து உள்ளீடுகளுக்கும் தனித்த மடக்கைக்கு ஒரு சீரற்ற பல்லுறுப்புக்கோவை நேர வழிமுறை உள்ளது. ஒரு சுழற்சிக் குழுவான G = {gi | 0 ≤ i <|G |} இன் ஜெனரேட்டர் g ஐப் பொறுத்தவரை, x இன் தனித்துவமான பதிவு அடிப்படை g க்கு x = gk உடன் முழு எண் k (0 ≤ k <|G |) ஆகும். {0,., |G | −1} இல் ஒரே மாதிரியாக விநியோகிக்க B ஐ எடுத்துக் கொள்ளுங்கள், பின்னர் xgB = gk + B G இல் ஒரே மாதிரியாக விநியோகிக்கப்படுகிறது. எனவே xgB x இலிருந்து சுயாதீனமாக உள்ளது, மேலும் அதன் மடக்கை பல்லுறுப்புக்கோவை நேரத்தில் நிகழ்தகவு 1/பாலி (n) உடன் கணக்கிடலாம். பின்னர் loggx ஷ்ண loggxgB-B (மாட் |G |) மற்றும் தனித்த மடக்கை சுய-குறைப்பு ஆகும். ஒரு மேட்ரிக்ஸின் நிரந்தரம் ஒரு மேட்ரிக்ஸின் நிரந்தர வரையறையைப் பொறுத்தவரை, எந்தவொரு n-பை-n மேட்ரிக்ஸ் M க்கும் PERM (M) என்பது M இல் உள்ள உள்ளீடுகளை விட டிகிரி n இன் பன்முக பல்லுறுப்புக்கோவை என்பது தெளிவாகிறது. ஒரு மேட்ரிக்ஸின் நிரந்தரத்தைக் கணக்கிடுவது கடினமான கணக்கீட்டு பணியாகும்-PERM #P-முழுமையானது (ஆதாரம்) என்று காட்டப்பட்டுள்ளது. மேலும், பெரும்பாலான மெட்ரிக்குகளுக்கு PERM (M) ஐக் கணக்கிடும் திறன் என்பது அனைத்து மெட்ரிக்குகளுக்கும் PERM (M) ஐக் கணக்கிடும் ஒரு சீரற்ற நிரலின் இருப்பைக் குறிக்கிறது. PERM சீரற்ற சுய குறைப்பு என்பதை இது நிரூபிக்கிறது. கீழே உள்ள விவாதம் சில பகா p க்கு ஒரு வரையறுக்கப்பட்ட புலம் Fp இலிருந்து மேட்ரிக்ஸ் உள்ளீடுகள் எங்கு வரையப்படுகின்றன என்பதையும், அந்த புலத்தில் அனைத்து எண்கணிதமும் எங்கு செய்யப்படுகிறது என்பதையும் கருத்தில் கொள்கிறது. X என்பது Fp இலிருந்து உள்ளீடுகளுடன் ஒரு சீரற்ற n-பை-n மேட்ரிக்ஸாக இருக்கட்டும். எந்தவொரு மேட்ரிக்ஸ் M + kX இன் அனைத்து உள்ளீடுகளும் k இன் நேரியல் செயல்பாடுகளாக இருப்பதால், PERM (M) ஐக் கணக்கிடும் டிகிரி n மல்டிவேரியேட் பல்லுறுப்புக்கோவையுடன் அந்த நேரியல் செயல்பாடுகளை உருவாக்குவதன் மூலம் k இல் மற்றொரு டிகிரி n பல்லுறுப்புக்கோவையைப் பெறுகிறோம், அதை நாம் p (k) என்று அழைப்போம். தெளிவாக, p (0) என்பது M இன் நிரந்தரத்திற்கு சமம். பெரும்பாலான n-பை-n மேட்ரிக்ஸ்களுக்கு PERM (A) இன் சரியான மதிப்பைக் கணக்கிடும் ஒரு நிரலை நாம் அறிவோம் என்று வைத்துக்கொள்வோம், அவற்றில் Fp---- குறிப்பாக, 1−1/(3n) இன் உள்ளீடுகளுடன். பின்னர் தோராயமாக மூன்றில் இரண்டு பங்கு நிகழ்தகவுடன், k = 1,2,., n + 1 க்கு PERM (M + kX) ஐக் கணக்கிடலாம். அந்த n + 1 மதிப்புகளை நாம் பெற்றவுடன், p (k) இன் குணகங்களுக்கு இடைக்கணிப்பைப் பயன்படுத்தி தீர்க்க முடியும் (p (k) க்கு டிகிரி n உள்ளது என்பதை நினைவில் கொள்ளுங்கள்). p (k) ஐ நாம் சரியாக அறிந்தவுடன், p (0) ஐ மதிப்பீடு செய்கிறோம், இது PERM (M) க்கு சமம். நாம் அவ்வாறு செய்தால், மூன்றில் ஒரு பங்கு தவறாகும் அபாயம் உள்ளது, ஆனால் பல சீரற்ற Xகளைத் தேர்ந்தெடுத்து மேலே உள்ள நடைமுறையை பல முறை மீண்டும் செய்வதன் மூலமும், பெரும்பான்மை வெற்றியாளருக்கு மட்டுமே பதிலை வழங்குவதன் மூலமும், பிழை விகிதத்தை மிகக் குறைவாக இயக்க முடியும். ஒரு NP-முழுமையான சிக்கல் தழுவிக்கொள்ள முடியாத சீரற்ற சுய-குறைப்பாக இருந்தால், பல்லுறுப்புக்கோவை வரிசைமுறை σ3 ஆக சரிந்துவிடும். ஒரு CoNP-கடினமான சிக்கல் O (log n/n) இல் சீரற்ற சுய-குறைப்பாக இருந்தால், σ2 = Π2. குறிப்புகள் எம். அபாடி, ஜே. ஃபைஜென்பாம் மற்றும் ஜே. கிலியன், ஆரக்கிளிலிருந்து தகவல்களை மறைப்பது குறித்து, ஜே. கம்ப்யூட். சிஸ்டம். அறிவியல்., 1989 எஸ். அரோரா, பிசிசி தேற்றத்தைச் சுற்றி, 1996 ஜே. ஃபைஜென்பாம், எல். ஃபோர்ட்னோ, முழுமையான தொகுப்புகளின் சீரற்ற-சுய-குறைப்பு, 1991 சீரற்ற வழிமுறைகள்