MAX-3SAT
میکس-3 ایس اے ٹی کمپیوٹر سائنس کے کمپیوٹیشنل پیچیدگی کے ذیلی شعبے میں ایک مسئلہ ہے۔ یہ بولین تسلی بخش مسئلہ (ایس اے ٹی) کو عام کرتا ہے جو کہ ایک فیصلہ سازی کا مسئلہ ہے جسے پیچیدگی کے نظریہ میں سمجھا جاتا ہے۔ اس کی تعریف اس طرح کی گئی ہے: 3-سی این ایف فارمولا φ (یعنی۔ فی شق زیادہ سے زیادہ 3 متغیرات کے ساتھ)، ایک ایسی تفویض تلاش کریں جو شقوں کی سب سے بڑی تعداد کو مطمئن کرے۔ MAX-3SAT پیچیدگی کلاس MAXSNP کے لیے ایک کینونکل مکمل مسئلہ ہے (پاپاڈیمیٹریو پی جی میں مکمل دکھایا گیا ہے۔ 314)۔ تخمینہ میکس-3 ایس اے ٹی کا فیصلہ ورژن این پی مکمل ہے۔ لہذا، کثیر الجہتی وقت کا حل صرف اس صورت میں حاصل کیا جا سکتا ہے جب P = NP ہو۔ 2 کے عنصر کے اندر ایک تخمینہ اس سادہ الگورتھم کے ساتھ حاصل کیا جا سکتا ہے، تاہم: اس حل کو آؤٹ پٹ کریں جس میں زیادہ تر شقیں مطمئن ہوں، جب یا تو تمام متغیرات = TRUE یا تمام متغیرات = FALSE ہوں۔ ہر شق کو دو حلوں میں سے کسی ایک سے مطمئن کیا جاتا ہے، اس لیے ایک حل کم از کم نصف شقوں کو مطمئن کرتا ہے۔ کارلوف-زوک الگورتھم کثیر الجہتی وقت میں چلتا ہے اور شقوں کے 7/8 کو مطمئن کرتا ہے۔ اگرچہ یہ الگورتھم بے ترتیب ہے، لیکن اسے اسی اندازے کی ضمانتوں کے ساتھ ایک تعیناتی (کثیر الجہتی وقت) الگورتھم حاصل کرنے کی تکنیکوں کا استعمال کرتے ہوئے اس سے الگ کیا جا سکتا ہے۔ تھیوریم 1 (غیر مطابقت پذیری) پی سی پی تھیوریم کا مطلب یہ ہے کہ ایک ε> 0 موجود ہے کہ MAX-3SAT کی (1-ε)-مطابقت NP-سخت ہے۔ ثبوت: پی سی پی تھیوریم کے ذریعہ کوئی بھی این پی مکمل مسئلہ۔ x ω L کے لیے، ایک 3-CNF فارمولا म्बाکس اس طرح بنایا گیا ہے کہ x ω L βx تسلی بخش ہو x β L βx کی (1-ε) m شقوں سے زیادہ تسلی بخش نہ ہوں۔ تصدیق کنندہ V تمام مطلوبہ بٹس کو ایک ساتھ پڑھتا ہے۔ غیر موافقت پذیر سوالات کرتا ہے۔ یہ درست ہے کیونکہ سوالات کی تعداد مستقل رہتی ہے۔ فرض کریں کہ q سوالات کی تعداد ہے۔ تمام بے ترتیب تاروں کی گنتی کرتے ہوئے، ہم ہر تار کی لمبائی سے پولی (x) تار حاصل کرتے ہیں۔ ہر Ri V کے لیے q پوزیشنیں i1,., iq اور ایک بولین فنکشن fR: {0,1} q-> {0,1} کا انتخاب کرتا ہے اور صرف اس صورت میں قبول کرتا ہے جب fR (π (i1,., iq)) ہو۔ یہاں π سے مراد اوریکل سے حاصل کردہ ثبوت ہے۔ اس کے بعد ہم اس کی تقلید کے لیے بولین فارمولا تلاش کرنے کی کوشش کرتے ہیں۔ ہم بولین متغیر x1،.، xl متعارف کراتے ہیں، جہاں l ثبوت کی لمبائی ہے۔ یہ ظاہر کرنے کے لیے کہ تصدیق کنندہ ممکنہ کثیر الجہتی وقت میں چلتا ہے، ہمیں تسلی بخش شقوں کی تعداد اور تصدیق کنندہ کے قبول کردہ امکان کے درمیان خط و کتابت کی ضرورت ہے۔ ہر R کے لیے، 2q SAT شقوں کا استعمال کرتے ہوئے fR (xi1،.، xiq) کی نمائندگی کرنے والی شقوں کو شامل کریں۔ لمبائی q کی شقوں کو نئے (معاون) متغیرات شامل کرکے لمبائی 3 میں تبدیل کیا جاتا ہے۔ x2. x10. x11. x12 = (x2. x10. yR) (R. x11. x12)۔ اس کے لیے زیادہ سے زیادہ q2q 3-SAT شقوں کی ضرورت ہوتی ہے۔ اگر z ω L ہے تو اس کا ایک ثبوت π ہے کہ Vπ (z) ہر Ri کے لیے قبول کرتا ہے۔ تمام شقیں مطمئن ہوتی ہیں اگر xi = π (i) اور معاون متغیرات کو صحیح طریقے سے شامل کیا جائے۔ اگر ان پٹ z′L ہے تو x1،.، xl اور yR کی ہر تفویض کے لیے، متعلقہ ثبوت π (i) = xi تصدیق کنندہ کو تمام R ω {0,1} r (|z |) کے نصف کے لیے مسترد کرنے کا سبب بنتا ہے۔ ہر آر کے لیے، ایف آر کی نمائندگی کرنے والی ایک شق ناکام ہو جاتی ہے۔ اس لیے شقوں کا ایک حصہ ناکام ہو جاتا ہے۔ یہ نتیجہ اخذ کیا جا سکتا ہے کہ اگر یہ ہر این پی مکمل مسئلے کے لیے درست ہے تو پی سی پی تھیوریم درست ہونا چاہیے۔ نظریہ 2 ہاسٹیڈ نظریہ 1 یعنی اس سے زیادہ سخت نتیجہ ظاہر کرتا ہے۔ ε کے لیے سب سے مشہور قدر۔ وہ 3-SAT کے لیے ایک پی سی پی تصدیق کنندہ بناتا ہے جو ثبوت سے صرف 3 بٹس پڑھتا ہے۔ ہر ε> 0 کے لیے، 3-SAT کے لیے ایک پی سی پی-تصدیق کنندہ M ہوتا ہے جو لمبائی کی بے ترتیب تار r کو پڑھتا ہے اور ثبوت π اور تھوڑا سا br میں استفسار کی پوزیشن ir، jr، kr کا حساب لگاتا ہے۔ یہ قبول کرتا ہے اگر اور صرف اس صورت میں جب 'π (ir) ωπ (jr) ωπ (kr) = br۔ تصدیق کنندہ میں تکمیل (1 − ε) اور ساؤنڈنیس 1/2 + ε ہے (پی سی پی (پیچیدگی) کا حوالہ دیں)۔ تصدیق کنندہ مطمئن ہوتا ہے اگر ان دونوں مساوات میں سے پہلی کو معمول کے مطابق "= 1" کے مساوی کیا جائے، تو کوئی لکیری مساوات کے نظام کو حل کر کے π کا ثبوت تلاش کر سکتا ہے (دیکھیں MAX-3LIN-EQN) جس کا مطلب P = NP ہے۔ اگر z ω L، تو شقوں کا ایک حصہ ω (1−ε) مطمئن ہے۔ اگر z′L، تو R کے (1/2 − ε) حصے کے لیے، 1/4 شقیں متضاد ہیں۔ یہ تخمینہ تناسب کی سختی کو ثابت کرنے کے لیے کافی ہے متعلقہ مسائل MAX-3SAT (B) MAX-3SAT کا محدود خصوصی معاملہ ہے جہاں ہر متغیر زیادہ سے زیادہ B شقوں میں ہوتا ہے۔ پی سی پی تھیوریم ثابت ہونے سے پہلے، پاپاڈیمیٹریو اور یاناککس نے دکھایا کہ کچھ فکسڈ مستقل بی کے لیے، یہ مسئلہ میکس ایس این پی-ہارڈ ہے۔ نتیجتا، پی سی پی تھیوریم کے ساتھ، یہ اے پی ایکس-ہارڈ بھی ہے۔ یہ مفید ہے کیونکہ میکس-3 ایس اے ٹی (بی) کو اکثر پی ٹی اے ایس کے تحفظ میں کمی حاصل کرنے کے لیے اس طرح استعمال کیا جا سکتا ہے جو میکس-3 ایس اے ٹی نہیں کر سکتا۔ بی کی واضح اقدار کے ثبوتوں میں شامل ہیں: تمام بی ≤ 13، سنجیو اروڑا، "ثبوتوں کی ممکنہ جانچ اور تخمینہ کے مسائل کی سختی"، اگست 1994 میں سی ایس ڈویژن، یو سی برکلے میں پیش کردہ مقالے کا نظر ثانی شدہ ورژن۔ CS-TR-476-94۔ سیکشن 2.2 اور تمام B ≤ 3 (جو سب سے بہتر ممکن ہے)۔ مزید برآں، اگرچہ فیصلہ کا مسئلہ 2 ایس اے ٹی کثیر الجہتی وقت میں حل کرنے کے قابل ہے، لیکن میکس-2 ایس اے ٹی (3) بھی اے پی ایکس سخت ہے۔ بی کے فنکشن کے طور پر میکس-3 ایس اے ٹی (بی) کے لیے بہترین ممکنہ تخمینہ تناسب کم از کم اور زیادہ سے زیادہ ہے، جب تک کہ این پی = آر پی نہ ہو۔ B کی بعض اقدار کے لیے لگ بھگ مستقل پر کچھ واضح حدود معلوم ہیں۔ برمن، کارپنسکی اور اسکاٹ نے ثابت کیا کہ میکس-3 ایس اے ٹی کی "اہم" مثالوں کے لیے جس میں ہر لفظی بالکل دو بار ہوتا ہے، اور ہر شق بالکل سائز 3 کی ہوتی ہے، مسئلہ کسی مستقل عنصر کے لیے تخمینہ مشکل ہے۔ میکس-ایک سیٹ میکس-3 سیٹ کا ایک پیرامیٹرائزڈ ورژن ہے جہاں ہر شق میں بالکل لفظی ہوتے ہیں، k "≤ 3 کے لیے۔ کوڈنگ تھیوری کے خیالات کا استعمال کرتے ہوئے تخمینہ تناسب کے ساتھ اس کا مؤثر انداز میں تخمینہ لگایا جا سکتا ہے۔ یہ ثابت ہو چکا ہے کہ میکس-3 ایس اے ٹی کی بے ترتیب مثالوں کا تخمینہ عنصر کے اندر لگایا جا سکتا ہے۔ حوالہ جات لیکچر نوٹ یونیورسٹی آف کیلیفورنیا، برکلے کا کوڈنگ تھیوری نوٹ یونیورسٹی ایٹ بفیلو میں اطمینان کے مسائل NP-سخت مسائل