Random self-reducibility
بے ترتیب خود تخفیف (آر ایس آر) یہ قاعدہ ہے کہ اوسط کیس کے لیے ایک اچھا الگورتھم بدترین کیس کے لیے ایک اچھا الگورتھم ظاہر کرتا ہے۔ آر ایس آر مثالوں کے ایک بڑے حصے کو حل کرکے کسی مسئلے کی تمام مثالوں کو حل کرنے کی صلاحیت ہے۔ تعریف اگر کسی فنکشن f کے لیے کسی بھی مثال x کی تشخیص کو کثیر الجہتی وقت میں ایک یا زیادہ بے ترتیب مثالوں yi پر f کی تشخیص تک کم کیا جا سکتا ہے، تو یہ خود تخفیف ہے (اسے غیر موافقت پذیر یکساں خود تخفیف بھی کہا جاتا ہے)۔ بے ترتیب خود تخفیف میں، f کے ڈومین میں ایک من مانی بدترین صورت مثال x کو بے ترتیب مثالوں کے سیٹ y1،.، yk پر نقشہ بنایا جاتا ہے۔ ایسا اس لیے کیا جاتا ہے کہ نقشہ سازی، x، اور f (y1)،.، f (yk) سے سکے ٹاس کی ترتیب کو دیکھتے ہوئے، کثیر الجہتی وقت میں f (x) کا حساب لگایا جا سکے۔ لہذا، yi پر محرک تقسیم کے حوالے سے اوسط کو لیتے ہوئے، f کی اوسط صورت کی پیچیدگی وہی ہے (کثیر الجہتی عوامل کے اندر) جو کہ f کی بدترین صورت کی بے ترتیب پیچیدگی ہے۔ ایک خاص بات یہ ہے کہ جب ہر بے ترتیب مثال yi کو f کے ڈومین میں عناصر کے پورے سیٹ پر یکساں طور پر تقسیم کیا جاتا ہے جس کی لمبائی |x | ہوتی ہے۔ اس صورت میں f اوسط پر اتنا ہی سخت ہے جتنا کہ بدترین صورت میں ہے۔ اس نقطہ نظر میں دو اہم پابندیاں شامل ہیں۔ سب سے پہلے y1،.، yk کی نسل غیر موافقت کے ساتھ انجام دی جاتی ہے۔ اس کا مطلب یہ ہے کہ y2 کو f (y1) کے معلوم ہونے سے پہلے اٹھایا جاتا ہے۔ دوسرا، یہ ضروری نہیں ہے کہ پوائنٹس y1,., yk کو یکساں طور پر تقسیم کیا جائے۔ کرپٹوگرافک پروٹوکول میں درخواست مسائل جن میں ڈیٹا میں کچھ رازداری کی ضرورت ہوتی ہے (عام طور پر کرپٹوگرافک مسائل) اس رازداری کو یقینی بنانے کے لیے بے ترتیب استعمال کر سکتے ہیں۔ در حقیقت، واحد ثابت طور پر محفوظ کرپٹوگرافک سسٹم (ون ٹائم پیڈ) کی سیکیورٹی سسٹم کو فراہم کردہ کلیدی ڈیٹا کی بے ترتیب پر مکمل طور پر انحصار کرتی ہے۔ کرپٹوگرافی کا میدان اس حقیقت کو استعمال کرتا ہے کہ بعض نمبر تھیوریٹک افعال تصادفی طور پر خود کو کم کرنے کے قابل ہیں۔ اس میں ممکنہ خفیہ کاری اور خفیہ نگاری کے لحاظ سے مضبوط سڈورینڈم نمبر جنریشن شامل ہیں۔ نیز، مثالوں کو چھپانے والی اسکیمیں (جہاں ایک کمزور نجی ڈیوائس اپنے ڈیٹا کو ظاہر کیے بغیر ایک مضبوط عوامی ڈیوائس کا استعمال کرتا ہے) بے ترتیب خود کٹوتیوں کی طرف سے آسانی سے مثال دی جاتی ہیں۔ مثالیں مجرد لوگرتھم کا مسئلہ، کواڈریٹک بقایا مسئلہ، آر ایس اے الٹا مسئلہ، اور میٹرکس کے مستقل حساب کتاب کا مسئلہ ہر بے ترتیب خود تخفیف کے مسائل ہیں۔ مجرد لوگرتھم تھیوریم: سائز |G | کا ایک چکور گروپ G دیا گیا ہے۔ اگر ایک متعین کثیر الجہتی ٹائم الگورتھم A تمام ان پٹ کے 1/پولی (n) فریکشن کے لیے مجرد لوگرتھم کا حساب لگاتا ہے (جہاں n = لاگ |G | ان پٹ سائز ہے)، تو تمام ان پٹ کے لیے مجرد لوگرتھم کے لیے ایک بے ترتیب کثیر الجہتی ٹائم الگورتھم ہوتا ہے۔ ایک چکور گروپ G = {gi | 0 ≤ i <|G |} کے جنریٹر g کو دیکھتے ہوئے، اور ایک x bul G، بیس g پر x کا مجرد لاگ انٹیجر k (0 ≤ k <|G |) ہے جس میں x = gk ہے۔ B کو یکساں طور پر تقسیم کرنے کے لیے {0،.، |G | −1} پر لیں، پھر xgB = gk + B بھی G پر یکساں طور پر تقسیم کیا جاتا ہے۔ لہذا xgB x سے آزاد ہے، اور اس کے لوگارتھم کا حساب کثیر الجہتی وقت میں امکان 1/پولی (n) کے ساتھ کیا جا سکتا ہے۔ پھر loggx ष्ण loggxgB-B (موڈ |G |) اور مجرد لوگرتھم خود کم کرنے کے قابل ہے۔ میٹرکس کی مستقل تعریف کو دیکھتے ہوئے، یہ واضح ہے کہ کسی بھی n-by-n میٹرکس M کے لیے PERM (M) M میں اندراجات پر ڈگری n کا ایک کثیر متغیر کثیر الجہتی ہے۔ میٹرکس کے مستقل کا حساب لگانا ایک مشکل کمپیوٹیشنل کام ہے-PERM کو #P-مکمل (ثبوت) دکھایا گیا ہے۔ مزید برآں، زیادہ تر میٹرکس کے لیے PERM (M) کا حساب لگانے کی صلاحیت ایک بے ترتیب پروگرام کے وجود کو ظاہر کرتی ہے جو تمام میٹرکس کے لیے PERM (M) کا حساب لگاتا ہے۔ یہ ظاہر کرتا ہے کہ PERM بے ترتیب خود تخفیف پذیر ہے۔ ذیل میں بحث اس معاملے پر غور کرتی ہے جہاں میٹرکس اندراجات کسی پرائم p کے لیے ایک محدود فیلڈ Fp سے تیار کیے جاتے ہیں، اور جہاں تمام ریاضی اس فیلڈ میں انجام دی جاتی ہے۔ X کو Fp سے اندراجات کے ساتھ ایک بے ترتیب n-by-n میٹرکس ہونے دیں۔ چونکہ کسی بھی میٹرکس M + kX کی تمام اندراجات k کے لکیری افعال ہیں، ان لکیری افعال کو ڈگری n ملٹی ویریٹ کثیر الجہتی کے ساتھ مرتب کرنے سے جو PERM (M) کا حساب لگاتا ہے ہمیں k پر ایک اور ڈگری n کثیر الجہتی ملتا ہے، جسے ہم p (k) کہیں گے۔ واضح طور پر، p (0) M کے مستقل کے برابر ہے۔ فرض کریں کہ ہم ایک ایسا پروگرام جانتے ہیں جو زیادہ تر n-by-n میٹرکس کے لیے PERM (A) کی صحیح قیمت کا حساب لگاتا ہے جس میں Fp---- خاص طور پر، 1−1/(3n) سے اندراجات ہوتے ہیں۔ پھر تقریبا دو تہائی کے امکان کے ساتھ، ہم k = 1,2,., n + 1 کے لیے PERM (M + kX) کا حساب لگا سکتے ہیں۔ ایک بار جب ہمارے پاس وہ n + 1 اقدار ہوں، تو ہم انٹرپولیشن کا استعمال کرتے ہوئے p (k) کے کوفشنٹس کے لیے حل کر سکتے ہیں (یاد رکھیں کہ p (k) کی ڈگری n ہے)۔ ایک بار جب ہم پی (کے) کو بالکل جان لیتے ہیں، تو ہم پی (0) کا اندازہ لگاتے ہیں، جو پی ای آر ایم (ایم) کے برابر ہے۔ اگر ہم ایسا کرتے ہیں، تو ہم ایک تہائی وقت غلط ہونے کا خطرہ مول لیتے ہیں، لیکن متعدد بے ترتیب ایکس کو چن کر اور مندرجہ بالا طریقہ کار کو کئی بار دہرا کر، اور صرف اکثریت کے فاتح کو جواب کے طور پر فراہم کر کے، ہم غلطی کی شرح کو بہت کم کر سکتے ہیں۔ نتائج اگر کوئی این پی مکمل مسئلہ غیر موافقت پذیر بے ترتیب خود تخفیف پذیر ہے تو کثیر الجہتی درجہ بندی σ3 پر گر جاتی ہے۔ اگر کوئی CoNP-سخت مسئلہ O (لاگ n/n) میں بے ترتیب خود کو کم کرنے کے قابل ہے تو σ2 = Π2۔ حوالہ جات ایم آبادی، جے فیجین بوم، اور جے کلیان، اوریکل سے معلومات چھپانے پر، جے کمپیوٹ۔ سیسٹ۔ سائنس.، 1989 ایس اروڑا، اراؤنڈ دی پی سی پی تھیوریم، 1996 جے فیجین بوم، ایل فورٹنو، آن دی رینڈم سیلف-ریڈکیوبلٹی آف کمپلیٹ سیٹس، 1991 رینڈمائزڈ الگورتھم