ذیلی سیٹوں کے جمع کرنے پر ایک اندازہ

فلپ جے ایرڈلسکی

3 ستمبر 2002

نوٹ: انٹرنیٹ کی تلاش نے آخر کار انکشاف کیا کہ یہ قیاس درست ہے اور اسے اسپنر کے نظریہ کے نام سے جانا جاتا ہے۔

کمبینیٹرکس میں یہ ایک مسئلہ ہے جس نے مجھے کئی سالوں سے پریشان کردیا ہے۔ شاید کوئی کمبینیٹر اس کو ایک ہی وقت میں حل کرسکتا ہے۔ میں نہیں کر سکتا تھا۔

ایک محدود سیٹ ایس آف این اشیاء پر غور کریں۔ ایک شمولیت کے بغیر جمع S اس طرح کے ذیلی سیٹ کا ایک مجموعہ C ہے کے مجموعہ میں کوئی اپسمچی مجموعہ میں کسی بھی دوسرے اپسمچی کو ایک مناسب اپسمچی ہے.

شامل کیے بغیر ایک قسم کا مجموعہ ایس کے تمام سنگل عنصری ذیلیوں کا مجموعہ ہے۔ دوسرا سبھی عنصر کے سب سیٹوں کا مجموعہ ہے۔ تاہم ، بہت سارے ، بہت سے دوسرے ہیں۔

یہاں قیاس ہے: N / 2-عنصر ذیلی ذخیرے میں شامل کیے بغیر کسی بھی دوسرے مجموعہ کی طرح کم از کم زیادہ سے زیادہ ذیلی ذخیرے شامل ہیں۔ اگر این عجیب ہے تو یہاں N / 2 کو اوپر یا نیچے گول کیا جاتا ہے۔ اس سے کوئی فرق نہیں پڑتا ، کیوں کہ دونوں صورتوں میں مجموعہ کا سائز ایک جیسا ہوتا ہے۔

جانور فورس کمپیوٹر کی طرف سے جانچ N. کی بہت چھوٹی اقدار کے لئے صرف اس گمان کی تصدیق کر سکتے ہیں ذیلی سیٹ کی تعداد P = 2 ہے N ، اور ذیلی سیٹ کے مجموعوں کی تعداد 2 ہے P بہت تیزی سے بہت بڑی ہو جاتا ہے، جس سے!

اس قیاس آرائی کو جنم دینے والی ایپلیکیشن شاید اب تک متروک ہے ، لیکن یہ یہاں ہے۔ یہاں پروم نام کی کوئی چیز ہوتی تھی (صرف قابل مطالعہ میموری) یہ تمام زیرو پر مشتمل تیار کیا گیا تھا۔ اندرونی رابطوں کو منتخب طور پر جلا دینے والی ایک خاص مشین کا استعمال کرکے ، صارف کسی بھی صفر کو ایک میں تبدیل کرسکتا ہے ، لیکن اس کے برعکس نہیں۔ اس کو پی آر او “جلانے” کہا جاتا تھا۔

اب فرض کیجئے کہ PROM کے ہر لفظ میں N بٹس ہیں۔ اگر آپ معلومات کوڈ کرتے ہیں تو ہر لفظ کے N / 2 بٹس بالکل اسی طرح تبدیل کردیئے جاتے ہیں ، معلومات کو تبدیل نہیں کیا جاسکتا ہے اور درست نہیں رہ سکتا ہے۔ اگر تمام N / 2-عنصر ذیلی ذخیروں کے مجموعہ سے بڑی شمولیت کے بغیر کوئی مجموعہ ہے تو ، ایسا کرنے کا ایک زیادہ موثر طریقہ موجود ہے۔