Structural complexity theory
کمپیوٹر سائنس کے کمپیوٹیشنل پیچیدگی کے نظریہ میں، ساختی پیچیدگی کا نظریہ یا محض ساختی پیچیدگی انفرادی مسائل اور الگورتھم کی کمپیوٹیشنل پیچیدگی کے بجائے پیچیدگی کی کلاسوں کا مطالعہ ہے۔ اس میں مختلف پیچیدگی کلاسوں کے اندرونی ڈھانچے اور مختلف پیچیدگی کلاسوں کے درمیان تعلقات دونوں کی تحقیق شامل ہے۔ یہ نظریہ اس قسم کے پہلے اور اب بھی سب سے اہم سوال، پی = این پی کے مسئلے کو حل کرنے کی (اب بھی ناکام) کوششوں کے نتیجے میں ابھرا ہے۔ زیادہ تر تحقیق اس مفروضے کی بنیاد پر کی جاتی ہے کہ پی این پی کے برابر نہیں ہے اور زیادہ دور رس قیاس آرائی پر کہ پیچیدگی کی کلاسوں کا کثیر الجہتی وقت کا درجہ بندی لامحدود ہے۔ اہم نتائج کمپریشن تھیوریم کمپریشن تھیوریم کمپیوٹیبل افعال کی پیچیدگی کے بارے میں ایک اہم تھیوریم ہے۔ تھیوریم میں کہا گیا ہے کہ کمپیوٹیبل باؤنڈری کے ساتھ کوئی سب سے بڑی پیچیدگی کلاس موجود نہیں ہے، جس میں تمام کمپیوٹیبل افعال شامل ہوں۔ خلائی درجہ بندی تھیوریم خلائی درجہ بندی تھیوریم علیحدگی کے نتائج ہیں جو یہ ظاہر کرتے ہیں کہ تعیناتی اور غیر تعیناتی دونوں مشینیں کچھ شرائط کے تابع (غیر علامتی طور پر) زیادہ جگہ میں مزید مسائل حل کر سکتی ہیں۔ مثال کے طور پر، ایک تعیناتی ٹورنگ مشین خلا n کے مقابلے خلا n لاگ n میں زیادہ فیصلہ سازی کے مسائل کو حل کر سکتی ہے۔ وقت کے لیے کچھ کمزور اینالاگس تھیوریمز وقت کی درجہ بندی تھیوریمز ہیں۔ ٹائم ہیرارکی تھیوریمز ٹورنگ مشینوں پر ٹائم باؤنڈ کمپیوٹیشن کے بارے میں اہم بیانات ہیں۔ غیر رسمی طور پر، ان نظریات کا کہنا ہے کہ زیادہ وقت دیا جائے تو ٹورنگ مشین مزید مسائل حل کر سکتی ہے۔ مثال کے طور پر، ایسے مسائل ہیں جنہیں n2 وقت کے ساتھ حل کیا جا سکتا ہے لیکن n وقت کے ساتھ نہیں۔ ویلینٹ-وزیرانی تھیوریم ویلینٹ-وزیرانی تھیوریم کمپیوٹیشنل پیچیدگی تھیوری میں ایک تھیوریم ہے۔ یہ لیسلی ویلینٹ اور وجے وزیرانی نے اپنے مقالے میں ثابت کیا تھا جس کا عنوان این پی اتنا ہی آسان ہے جتنا کہ 1986 میں شائع ہونے والے منفرد حل کا پتہ لگانا۔ نظریہ بیان کرتا ہے کہ اگر غیر متزلزل-SAT کے لیے کثیر الجہتی وقت الگورتھم ہے، تو NP = RP۔ ثبوت ملمولی-وزیرانی آئسولیشن لیما پر مبنی ہے، جسے بعد میں نظریاتی کمپیوٹر سائنس میں متعدد اہم ایپلی کیشنز کے لیے استعمال کیا گیا۔ سیپسر-لاؤٹیمین تھیوریم سیپسر-لاؤٹیمین تھیوریم یا سیپسر-گاکس-لاؤٹیمین تھیوریم بیان کرتا ہے کہ باؤنڈ ایرر پروبیبلسٹک پولینومیل (بی پی پی) ٹائم، پولینومیل ٹائم ہیرارکی میں موجود ہے، اور زیادہ خاص طور پر σ2 θ Π2۔ ساوچ کا نظریہ ساوچ کا نظریہ، جسے والٹر ساوچ نے 1970 میں ثابت کیا، تعیناتی اور غیر تعیناتی خلائی پیچیدگی کے درمیان تعلق فراہم کرتا ہے۔ اس میں کہا گیا ہے کہ کسی بھی فنکشن کے لیے، ٹوڈا کا تھیوریم ٹوڈا کا تھیوریم ایک ایسا نتیجہ ہے جسے سینوسوکے ٹوڈا نے اپنے مقالے "پی پی از اس ہارڈ ایز دی پولینومیل ٹائم ہائیرارکی" (1991) میں ثابت کیا تھا اور اسے 1998 کا گوڈل انعام دیا گیا تھا۔ تھیوریم میں کہا گیا ہے کہ پوری کثیر الجہتی درجہ بندی پی ایچ پی پی پی میں موجود ہے۔ اس سے ایک قریب سے متعلق بیان ظاہر ہوتا ہے، کہ پی ایچ P#P میں موجود ہے۔ ایمرمین-زیلپسینی تھیوریم امرمین-زیلپسینی تھیوریم کو 1987 میں نیل ایمرمین اور رابرٹ زیلپسینی نے آزادانہ طور پر ثابت کیا تھا، جس کے لیے انہوں نے 1995 کا گوڈل انعام مشترکہ طور پر حاصل کیا تھا۔ اس کی عمومی شکل میں تھیوریم بیان کرتا ہے کہ کسی بھی فنکشن s (n) ≤ لاگ n کے لیے NSPACE (s (n)) = co-NSPACE (s (n))۔ نتیجہ برابر طور پر NFL = co-NSL کے طور پر بیان کیا جاتا ہے۔ اگرچہ یہ خاص معاملہ ہے جب s (n) = لاگ n، یہ ایک معیاری پیڈنگ دلیل کے ذریعے عمومی تھیوریم کو ظاہر کرتا ہے۔ نتیجہ نے دوسرا ایل بی اے مسئلہ حل کر دیا۔ تحقیقی موضوعات اس شعبے میں تحقیق کی اہم سمتوں میں شامل ہیں: پیچیدگی کے بارے میں مختلف حل نہ ہونے والے مسائل سے پیدا ہونے والے مضمرات کا مطالعہ کلاسوں میں مختلف قسم کی وسائل سے محدود کمی کا مطالعہ اور متعلقہ مکمل زبانیں مختلف پابندیوں کے نتائج کا مطالعہ اور ذخیرہ کرنے اور ڈیٹا تک رسائی کے طریقہ کار۔ حوالہ جات