Fagin's theorem
فگین کا نظریہ وضاحتی پیچیدگی کے نظریہ کا سب سے قدیم نتیجہ ہے، جو کمپیوٹیشنل پیچیدگی کے نظریہ کی ایک شاخ ہے جو پیچیدگی کی کلاسوں کو ان مسائل کو حل کرنے کے لیے الگورتھم کے رویے کے بجائے ان کے مسائل کی منطق پر مبنی وضاحت کے لحاظ سے نمایاں کرتی ہے۔ تھیوریم میں کہا گیا ہے کہ وجودی دوسرے درجے کی منطق میں ظاہر ہونے والی تمام خصوصیات کا مجموعہ قطعی طور پر پیچیدگی کلاس NP ہے۔ یہ 1973 میں رونالڈ فگین نے اپنے ڈاکٹریٹ کے مقالے میں ثابت کیا تھا، اور اپنے 1974 کے مقالے میں ظاہر ہوتا ہے۔ دوسرے درجے کے فارمولے کے ذریعہ درکار آرٹی کو (ایک سمت میں) بہتر بنایا گیا تھا، اور گرینڈ جین کے کئی نتائج نے غیر متعین بے ترتیب رسائی والی مشینوں پر سخت حدود فراہم کی ہیں۔ ثبوت فگین کے 1974 کے مقالے کے علاوہ، نظریہ کا تفصیلی ثبوت فراہم کرتا ہے۔ یہ ظاہر کرنا سیدھا ہے کہ ہر وجودی دوسرے درجے کے فارمولے کو این پی میں غیر متعین طور پر تمام وجودی طور پر اہل متغیرات کی قدر کا انتخاب کرکے پہچانا جا سکتا ہے، لہذا ثبوت کا بنیادی حصہ یہ ظاہر کرنا ہے کہ این پی میں ہر زبان کو ایک وجودی دوسرے درجے کے فارمولے سے بیان کیا جا سکتا ہے۔ ایسا کرنے کے لیے، کوئی بھی من مانی طور پر کمپیوٹیشن ٹیبلو کا انتخاب کرنے کے لیے دوسرے درجے کے وجودی مقداری کا استعمال کر سکتا ہے۔ مزید تفصیل سے، غیر متعین ٹورنگ مشین کے ایک ایگزیکیوشن ٹریس کے ہر ٹائم اسٹیپ کے لیے، یہ جھانکی ٹورنگ مشین کی حالت، ٹیپ میں اس کی پوزیشن، ہر ٹیپ سیل کے مندرجات، اور اس مرحلے پر مشین کون سا غیر متعین انتخاب کرتی ہے، کو انکوڈ کرتی ہے۔ ایک فرسٹ آرڈر فارمولا اس انکوڈ شدہ معلومات کو محدود کر سکتا ہے تاکہ یہ ایک درست عمل درآمد کا سراغ بیان کرے، جس میں ٹیپ کے مندرجات اور ٹورنگ مشین کی حالت اور ہر ٹائم اسٹیپ پر پوزیشن پچھلے ٹائم اسٹیپ سے پیروی کرتی ہے۔ ثبوت میں استعمال ہونے والا ایک کلیدی لیما یہ ہے کہ کائنات پر تعلق کے طور پر لمبائی کی لکیری ترتیب (جیسے کہ ٹائم اسٹیپس کے لکیری آرڈرز اور کسی بھی ٹائم اسٹیپ پر ٹیپ کے مندرجات) کو انکوڈ کرنا ممکن ہے۔ اس کو حاصل کرنے کا ایک طریقہ یہ ہے کہ ایک لکیری ترتیب کا انتخاب کیا جائے اور پھر اسے احترام کے ساتھ لغت کی ترتیب کے طور پر بیان کیا جائے۔