Circuit satisfiability problem
نظریاتی کمپیوٹر سائنس میں، سرکٹ کی اطمینان کا مسئلہ (جسے CIRCUIT-SAT، سرکٹ SAT، CSAT، وغیرہ بھی کہا جاتا ہے) یہ فیصلہ کرنے کا مسئلہ ہے کہ آیا کسی دیئے گئے بولین سرکٹ کے پاس اس کے ان پٹ کی تفویض ہے جو آؤٹ پٹ کو درست بناتی ہے۔ دوسرے لفظوں میں، یہ پوچھتا ہے کہ کیا کسی دیئے گئے بولین سرکٹ کے ان پٹ کو مستقل طور پر 1 یا 0 پر سیٹ کیا جا سکتا ہے تاکہ سرکٹ 1 آؤٹ پٹ کرے۔ اگر ایسا ہے تو سرکٹ کو تسلی بخش کہا جاتا ہے۔ ورنہ، سرکٹ کو غیر تسلی بخش کہا جاتا ہے۔ دائیں طرف کے اعداد و شمار میں، بائیں سرکٹ کو دونوں ان پٹ کو 1 ترتیب دے کر مطمئن کیا جا سکتا ہے، لیکن دائیں سرکٹ غیر تسلی بخش ہے۔ سرکٹ ایس اے ٹی کا بولین تسلی بخش مسئلہ (ایس اے ٹی) سے گہرا تعلق ہے، اور اسی طرح، این پی مکمل ثابت ہوا ہے۔ یہ ایک پروٹوٹائپکل این پی مکمل مسئلہ ہے۔ کک-لیون تھیوریم کو بعض اوقات ایس اے ٹی کے بجائے سرکٹ ایس اے ٹی پر ثابت کیا جاتا ہے، اور پھر سرکٹ ایس اے ٹی کو ان کے این پی مکمل ہونے کو ثابت کرنے کے لیے دیگر اطمینان بخش مسائل تک کم کیا جا سکتا ہے۔ صوابدیدی بائنری گیٹس پر مشتمل سرکٹ کی اطمینان کا فیصلہ وقت پر کیا جا سکتا ہے۔ این پی-تکمیل کا ثبوت ایک سرکٹ اور ان پٹ کے تسلی بخش سیٹ کو دیکھتے ہوئے، کوئی بھی مستقل وقت میں ہر گیٹ کی آؤٹ پٹ کا حساب لگا سکتا ہے۔ لہذا، سرکٹ کی آؤٹ پٹ کثیر الجہتی وقت میں قابل تصدیق ہے۔ اس طرح سرکٹ ایس اے ٹی کا تعلق پیچیدگی کلاس این پی سے ہے۔ این پی سختی کو ظاہر کرنے کے لیے، 3 ایس اے ٹی سے سرکٹ ایس اے ٹی میں کمی کرنا ممکن ہے۔ فرض کریں کہ اصل 3SAT فارمولے میں متغیر، اور آپریٹرز (AND، OR، NOT) ہیں۔ ایک سرکٹ اس طرح ڈیزائن کریں کہ اس میں ہر متغیر کے مطابق ایک ان پٹ اور ہر آپریٹر کے مطابق ایک گیٹ ہو۔ 3 ایس اے ٹی فارمولے کے مطابق دروازوں کو جوڑیں۔ مثال کے طور پر، اگر 3 ایس اے ٹی فارمولا ہے تو سرکٹ میں 3 ان پٹ ہوں گے، ایک AND، ایک OR، اور ایک NOT گیٹ۔ متعلقہ ان پٹ کو AND گیٹ پر بھیجنے سے پہلے الٹا کیا جائے گا اور AND گیٹ کی آؤٹ پٹ کو OR گیٹ پر بھیجا جائے گا جس میں نوٹ کریں کہ 3SAT فارمولا اوپر بنائے گئے سرکٹ کے مساوی ہے، اس لیے ان کی آؤٹ پٹ اسی ان پٹ کے لیے یکساں ہے۔ لہذا، اگر 3 ایس اے ٹی فارمولے میں تسلی بخش تفویض ہے، تو متعلقہ سرکٹ 1 آؤٹ پٹ کرے گا، اور اس کے برعکس۔ تو، یہ ایک درست کمی ہے، اور سرکٹ SAT NP-سخت ہے۔ یہ اس ثبوت کو مکمل کرتا ہے کہ سرکٹ SAT NP مکمل ہے۔ محدود متغیرات اور متعلقہ مسائل پلانر سرکٹ SAT فرض کریں کہ ہمیں ایک پلانر بولین سرکٹ دیا گیا ہے (یعنی۔ ایک بولین سرکٹ جس کا بنیادی گراف پلانر ہے) جس میں صرف دو ان پٹ والے NAND گیٹ ہوتے ہیں۔ پلانر سرکٹ ایس اے ٹی اس بات کا تعین کرنے کا فیصلہ مسئلہ ہے کہ آیا اس سرکٹ کے پاس اس کے ان پٹ کی تفویض ہے جو آؤٹ پٹ کو درست بناتی ہے۔ یہ مسئلہ این پی مکمل ہے۔ مزید برآں، اگر پابندیوں کو تبدیل کیا جاتا ہے تاکہ سرکٹ میں کوئی بھی گیٹ این او آر گیٹ ہو، تو اس کے نتیجے میں پیدا ہونے والا مسئلہ این پی مکمل رہتا ہے۔ سرکٹ یو این ایس اے ٹی سرکٹ یو این ایس اے ٹی اس بات کا تعین کرنے کا فیصلہ کرنے کا مسئلہ ہے کہ آیا دیا ہوا بولین سرکٹ اپنے ان پٹ کی تمام ممکنہ تفویض کے لیے غلط آؤٹ پٹ دیتا ہے۔ یہ سرکٹ ایس اے ٹی کے مسئلے کی تکمیل ہے، اور اس لیے کو-این پی مکمل ہے۔ سرکٹ ایس اے ٹی یا اس کے متغیرات سے سرکٹ ایس اے ٹی میں کمی کو بعض مسائل کی این پی سختی کو ظاہر کرنے کے لیے استعمال کیا جا سکتا ہے، اور ہمیں دوہری ریل اور بائنری منطق میں کمی کا متبادل فراہم کرتا ہے۔ اس طرح کے تخفیف کے لیے جن آلات کی تعمیر کی ضرورت ہے وہ ہیں: ایک تار والا گیجٹ۔ یہ گیجٹ سرکٹ میں تاروں کی تقلید کرتا ہے۔ ایک تقسیم شدہ گیجٹ۔ یہ گیجٹ اس بات کی ضمانت دیتا ہے کہ تمام آؤٹ پٹ تاروں کی قیمت ان پٹ تار کے برابر ہے۔ سرکٹ کے دروازوں کی تقلید کرنے والے گیجٹ۔ ایک حقیقی ٹرمینیٹر گیجٹ۔ یہ گیجٹ پورے سرکٹ کی آؤٹ پٹ کو سچ ہونے پر مجبور کرنے کے لیے استعمال ہوتا ہے۔ ایک ٹرن گیجٹ۔ یہ گیجٹ ہمیں ضرورت کے مطابق صحیح سمت میں تاروں کو ری ڈائریکٹ کرنے کی اجازت دیتا ہے۔ ایک کراس اوور گیجٹ۔ یہ گیجٹ ہمیں دو تاروں کو تعامل کے بغیر ایک دوسرے کو عبور کرنے کی اجازت دیتا ہے۔ مائن سویپر انفریشن کا مسئلہ یہ مسئلہ پوچھتا ہے کہ کیا مائن سویپر بورڈ دیے جانے پر تمام بموں کا پتہ لگانا ممکن ہے۔ سرکٹ یو این ایس اے ٹی کے مسئلے میں کمی کے ذریعے یہ سی او این پی مکمل ثابت ہوا ہے۔ اس تخفیف کے لیے بنائے گئے آلات یہ ہیں: تار، تقسیم، اور نہ کہ دروازے اور ٹرمینیٹر۔ ان آلات کے حوالے سے تین اہم مشاہدات ہیں۔ سب سے پہلے، اسپلٹ گیجٹ کو ناٹ گیجٹ اور ٹرن گیجٹ کے طور پر بھی استعمال کیا جا سکتا ہے۔ دوسرا، اینڈ اور ناٹ گیجٹ بنانا کافی ہے، کیونکہ وہ مل کر یونیورسل نینڈ گیٹ کی تقلید کر سکتے ہیں۔ آخر میں، چونکہ ایک ایکس او آر کو لاگو کرنے کے لیے تین این اے این ڈی کو انٹرسیکشن فری بنایا جا سکتا ہے، اور چونکہ ایکس او آر کراس اوور بنانے کے لیے کافی ہے، اس سے ہمیں مطلوبہ کراس اوور گیجٹ ملتا ہے۔ سیٹین کی تبدیلی سیٹین کی تبدیلی سرکٹ-ایس اے ٹی سے ایس اے ٹی میں براہ راست کمی ہے۔ اس تبدیلی کو بیان کرنا آسان ہے اگر سرکٹ مکمل طور پر 2-ان پٹ نینڈ گیٹس (بولین آپریٹرز کا ایک فعال طور پر مکمل سیٹ) سے بنایا گیا ہے: سرکٹ میں ہر نیٹ کو ایک متغیر تفویض کریں، پھر ہر نینڈ گیٹ کے لیے، کنجکٹو نارمل فارم کلازز (v1wv3) (v2v3) (¬v1wv2v3) بنائیں، جہاں v1 اور v2 نینڈ گیٹ کے لیے ان پٹ ہیں اور v3 آؤٹ پٹ ہے۔ یہ شقیں تینوں متغیرات کے درمیان تعلق کو مکمل طور پر بیان کرتی ہیں۔ تمام دروازوں سے شقوں کو ایک اضافی شق کے ساتھ جوڑنا جو سرکٹ کے آؤٹ پٹ متغیر کو درست ہونے پر مجبور کرتا ہے، کمی کو مکمل کرتا ہے۔ تمام رکاوٹوں کو پورا کرنے والے متغیرات کی تفویض صرف اس صورت میں موجود ہے جب اصل سرکٹ تسلی بخش ہو، اور کوئی بھی حل ان پٹ کو تلاش کرنے کے اصل مسئلے کا حل ہو جو سرکٹ آؤٹ پٹ کو 1 بناتا ہے۔ اس کے برعکس-کہ ایس اے ٹی سرکٹ-ایس اے ٹی کے لیے قابل تخفیف ہے-بولین فارمولے کو سرکٹ کے طور پر دوبارہ لکھ کر اور اسے حل کر کے معمولی طور پر پیروی کرتا ہے۔ سرکٹ ویلیو پروبلم اسٹرکچرڈ سرکٹ اطمینان بخش اطمینان بخش مسئلہ حوالہ جات این پی مکمل مسائل کمپیوٹیشنل مسائل کمپیوٹیبلٹی تھیوری بھی دیکھیں۔