P-complete
کمپیوٹیشنل پیچیدگی کے نظریہ میں، ایک فیصلہ مسئلہ P-مکمل (پیچیدگی کلاس P کے لیے مکمل) ہے اگر یہ P میں ہے اور P میں ہر مسئلہ کو مناسب کمی کے ذریعے اس میں کم کیا جا سکتا ہے۔ پی-مکمل فیصلہ کے مسائل کا تصور اس کے تجزیے میں مفید ہے: کن مسائل کو مؤثر طریقے سے متوازی بنانا مشکل ہے، کن مسائل کو محدود جگہ میں حل کرنا مشکل ہے۔ خاص طور پر جب پولی ٹائم کم کرنے کے مقابلے میں کم کرنے کے مضبوط تصورات پر غور کیا جائے۔ استعمال کی جانے والی مخصوص قسم کی کمی مختلف ہوتی ہے اور مسائل کے عین مطابق سیٹ کو متاثر کر سکتی ہے۔ عام طور پر، کثیر الجہتی وقت کی کمی سے زیادہ مضبوط کمی کا استعمال کیا جاتا ہے، کیونکہ P میں تمام زبانیں (خالی زبان اور تمام تاروں کی زبان کے علاوہ) کثیر الجہتی وقت کی کمی کے تحت P مکمل ہوتی ہیں۔ اگر ہم این سی ریڈوکشنز یعنی ریڈوکشنز کا استعمال کرتے ہیں جو پروسیسرز کی کثیر تعداد کے ساتھ متوازی کمپیوٹر پر پولی لوگرتھمک وقت میں کام کر سکتے ہیں، تو تمام پی-مکمل مسائل این سی سے باہر ہوتے ہیں اور اس لیے غیر مصدقہ مفروضے کے تحت مؤثر طریقے سے متوازی نہیں کیا جا سکتا کہ این سی۔ اگر ہم مضبوط لاگ-اسپیس میں کمی کا استعمال کرتے ہیں، تو یہ درست رہتا ہے، لیکن اس کے علاوہ ہم یہ بھی سیکھتے ہیں کہ تمام پی-مکمل مسائل کمزور غیر مصدقہ مفروضے کے تحت ایل سے باہر ہوتے ہیں کہ ایل۔ اس مؤخر الذکر صورت میں سیٹ پی-مکمل چھوٹا ہو سکتا ہے۔ تحریک کلاس پی، جسے عام طور پر ترتیب وار کمپیوٹر کے لیے تمام "ٹریک ایبل" مسائل پر مشتمل سمجھا جاتا ہے، کلاس این سی پر مشتمل ہوتا ہے، جو ان مسائل پر مشتمل ہوتا ہے جنہیں متوازی کمپیوٹر پر مؤثر طریقے سے حل کیا جا سکتا ہے۔ اس کی وجہ یہ ہے کہ متوازی کمپیوٹرز کو ترتیب وار مشین پر نقل کیا جا سکتا ہے۔ یہ معلوم نہیں ہے کہ آیا این سی = پی۔ دوسرے لفظوں میں، یہ معلوم نہیں ہے کہ آیا کوئی قابل علاج مسائل ہیں جو فطری طور پر ترتیب وار ہیں۔ جس طرح یہ بڑے پیمانے پر شبہ کیا جاتا ہے کہ پی این پی کے برابر نہیں ہے، اسی طرح یہ بھی بڑے پیمانے پر شبہ کیا جاتا ہے کہ این سی پی کے برابر نہیں ہے۔ اسی طرح، کلاس ایل میں وہ تمام مسائل شامل ہیں جنہیں لوگرتھمک اسپیس میں ترتیب وار کمپیوٹر کے ذریعے حل کیا جا سکتا ہے۔ ایسی مشینیں کثیر الجہتی وقت میں چلتی ہیں کیونکہ ان میں ترتیبات کی کثیر الجہتی تعداد ہو سکتی ہے۔ یہ شبہ کیا جاتا ہے کہ L ष्णپ ؛ یعنی، کہ کچھ مسائل جنہیں کثیر الجہتی وقت میں حل کیا جا سکتا ہے، ان کے لیے بھی لوگرتھمک جگہ سے زیادہ کی ضرورت ہوتی ہے۔ اسی طرح پی = این پی سوال کا تجزیہ کرنے کے لیے این پی-مکمل مسائل کے استعمال کے لیے، پی-مکمل مسائل، جنہیں "شاید متوازی نہیں" یا "شاید فطری طور پر ترتیب وار" مسائل کے طور پر دیکھا جاتا ہے، این سی = پی سوال کا مطالعہ کرنے کے لیے اسی طرح کام کرتے ہیں۔ کسی پی-مکمل مسئلے کے حل کو متوازی بنانے کا ایک موثر طریقہ تلاش کرنا ظاہر کرے گا کہ این سی = پی۔ اسے "سپر لوگرتھمک اسپیس کی ضرورت والے مسائل" کے طور پر بھی سوچا جا سکتا ہے۔ پی-مکمل مسئلے کا لاگ اسپیس حل (لاگ اسپیس میں کمی پر مبنی تعریف کا استعمال کرتے ہوئے) کا مطلب ایل = پی ہوگا۔ اس کے پیچھے کی منطق اس منطق سے مشابہت رکھتی ہے کہ این پی-مکمل مسئلے کا کثیر الجہتی وقت کا حل پی = این پی ثابت کرے گا: اگر ہمارے پاس پی میں کسی بھی مسئلے سے مسئلہ اے میں این سی کی کمی ہے، اور اے کے لیے این سی حل ہے، تو این سی = پی۔ اسی طرح، اگر ہمارے پاس پی میں کسی بھی مسئلے سے مسئلہ اے میں لاگ اسپیس کی کمی ہے، اور ایک لاگ-اسپیس حل ہے۔ پی میں کسی بھی ایکس کے لیے، ٹورنگ مشین کی انکوڈنگ کو آؤٹ پٹ کریں جو اسے کثیر الجہتی وقت میں قبول کرتی ہے، خود ایکس کی انکوڈنگ، اور پی سے مطابقت رکھنے والے کئی مراحل جو ٹورنگ مشین کے فیصلہ کرنے کے عمل پر کثیر الجہتی وقت پابند ہیں،۔ مشین M اقدامات کے اندر x پر رکتی ہے اگر اور صرف اس صورت میں جب x L میں ہو۔ واضح طور پر، اگر ہم ایک ترتیب وار کمپیوٹر کے عمومی تخروپن کو متوازی بنا سکتے ہیں (یعنی۔ ٹورنگ مشین کا تخروپن)، پھر ہم اس کمپیوٹر پر چلنے والے کسی بھی پروگرام کو متوازی بنا سکیں گے۔ اگر یہ مسئلہ این سی میں ہے، تو پی میں ہر دوسرا مسئلہ بھی ایسا ہی ہے۔ اگر مراحل کی تعداد بائنری میں لکھی گئی ہے، تو مسئلہ ایکس پی ٹی آئی ایم ای مکمل ہے۔ یہ مسئلہ P-تکمیل کے نظریہ میں ایک عام چال کی وضاحت کرتا ہے۔ ہمیں واقعی اس میں دلچسپی نہیں ہے کہ آیا متوازی مشین پر کسی مسئلے کو تیزی سے حل کیا جا سکتا ہے۔ ہمیں صرف اس میں دلچسپی ہے کہ آیا کوئی متوازی مشین اسے ترتیب وار مشین سے کہیں زیادہ تیزی سے حل کرتی ہے۔ لہذا، ہمیں مسئلہ کو دوبارہ لکھنا ہوگا تاکہ ترتیب وار ورژن P میں ہو۔ اسی وجہ سے اس مسئلہ کے لیے T کو یونری میں لکھنے کی ضرورت تھی۔ اگر ایک عدد T کو بائنری عدد کے طور پر لکھا جائے (n اور صفر کی ایک تار، جہاں n = لاگ T)، تو واضح ترتیب وار الگورتھم میں 2n وقت لگ سکتا ہے۔ دوسری طرف، اگر T کو ایک یونیری نمبر (n کی ایک سٹرنگ، جہاں n = T) کے طور پر لکھا جائے، تو اس میں صرف n وقت لگتا ہے۔ T کو بائنری کے بجائے یونیری میں لکھنے سے، ہم نے واضح ترتیب وار الگورتھم کو ایکسپونینشیل ٹائم سے لکیری ٹائم تک کم کر دیا ہے۔ اس سے ترتیب وار مسئلہ پی میں آتا ہے۔ پھر، یہ این سی میں ہوگا اگر اور صرف اس صورت میں جب یہ متوازی ہو۔ بہت سے دوسرے مسائل پی-مکمل ثابت ہوئے ہیں، اور اس وجہ سے بڑے پیمانے پر یہ خیال کیا جاتا ہے کہ وہ فطری طور پر ترتیب وار ہیں۔ ان میں درج ذیل مسائل شامل ہیں جو کم از کم لاگ اسپیس میں کمی کے تحت پی مکمل ہیں، یا تو جیسا کہ دیا گیا ہے، یا فیصلہ مسئلہ کی شکل میں: سرکٹ ویلیو پروبلم (سی وی پی)-ایک سرکٹ کو دیکھتے ہوئے، سرکٹ میں ان پٹ، اور سرکٹ میں ایک گیٹ، اس گیٹ کی آؤٹ پٹ کا حساب لگائیں۔ سی وی پی کا محدود کیس-سی وی پی کی طرح، سوائے ہر گیٹ کے دو ان پٹ اور دو آؤٹ پٹ (ایف اور ایف نہیں) کے، ہر دوسری پرت صرف اینڈ گیٹ ہے، باقی او آر گیٹ ہیں (یا، مساوی طور پر، تمام دروازے این اے این ڈی گیٹ ہیں، یا تمام دروازے این او آر گیٹ ہیں)، گیٹ کے ان پٹ فوری طور پر پچھلی پرت لکیری پروگرامنگ سے آتے ہیں-لکیری عدم مساوات کی رکاوٹوں کے تابع لکیری فنکشن کو زیادہ سے زیادہ کریں۔ لغت کے لحاظ سے پہلی گہرائی پہلی تلاش کا حکم-مقررہ ترتیب شدہ ملحقہ فہرستوں کے ساتھ ایک گراف کو دیکھتے ہوئے، اور نوڈس یو اور وی، کیا عمودی یو کا دورہ عمودی وی سے پہلے گہرائی میں کیا جاتا ہے-ملحقہ فہرستوں کی ترتیب سے متاثر پہلی تلاش؟ سیاق و سباق سے پاک گرائمر ممبرشپ-سیاق و سباق سے پاک گرائمر اور سٹرنگ کو دیکھتے ہوئے، کیا وہ سٹرنگ اس گرائمر سے تیار کی جا سکتی ہے؟ ہارن کی اطمینان-ہارن شقوں کے ایک سیٹ کو دیکھتے ہوئے، کیا کوئی متغیر تفویض ہے جو انہیں مطمئن کرتی ہے؟ یہ بولین اطمینان کے مسئلے کا پی کا ورژن ہے۔ گیم آف لائف-کونوے کے گیم آف لائف، ایک مخصوص خلیہ، اور ایک ٹائم ٹی (یونری میں) کی ابتدائی ترتیب کو دیکھتے ہوئے، کیا وہ خلیہ ٹی مراحل کے بعد زندہ ہے؟ LZW (الگورتھم) (1978 پیراڈائم) ڈیٹا کمپریشن-سٹرنگ s اور t کو دیکھتے ہوئے، کیا LZ78 طریقہ کار کے ساتھ s کو کمپریس کرنا لغت میں t کا اضافہ کرے گا؟ (نوٹ کریں کہ LZ77 کمپریشن جیسے جی زپ کے لیے، یہ بہت آسان ہے، کیونکہ مسئلہ کم ہو کر "Is t in s?" ہو جاتا ہے۔) جزوی اقسام کے لیے قیاس ٹائپ کریں-لیمبڈا کیلکولس سے ایک غیر ٹائپ شدہ اصطلاح کو دیکھتے ہوئے، اس بات کا تعین کریں کہ آیا اس اصطلاح کی جزوی قسم ہے۔ اوپر دی گئی زیادہ تر زبانیں کمی کے اور بھی مضبوط تصورات کے تحت P-مکمل ہیں، جیسے کہ یکساں کئی-ایک کمی، DLOGTIME کمی، یا پولی لوگرتھمک پروجیکشن۔ یہ ثابت کرنے کے لیے کہ P میں دیا گیا مسئلہ P-مکمل ہے، عام طور پر ایک معروف P-مکمل مسئلہ کو دیئے گئے مسئلے تک کم کرنے کی کوشش کی جاتی ہے۔ 1999 میں، جن یی کائی اور ڈی سیوکمار نے اوگیہار کے کام کی بنیاد پر یہ ظاہر کیا کہ اگر کوئی غیر معمولی زبان موجود ہے جو پی مکمل ہے، تو ایل = پی پی مکمل مسائل مختلف وقت کی پیچیدگیوں کے ساتھ حل ہو سکتے ہیں۔ مثال کے طور پر، سرکٹ ویلیو کے مسئلے کو ٹپوولوجیکل ترتیب کے ذریعے لکیری وقت میں حل کیا جا سکتا ہے۔ یقینا، کیونکہ پی-مکمل مسئلے میں کمی میں وقت کی پیچیدگیاں مختلف ہو سکتی ہیں، اس حقیقت کا مطلب یہ نہیں ہے کہ پی میں موجود تمام مسائل کو بھی لکیری وقت میں حل کیا جا سکتا ہے۔ کچھ این پی مسائل کو این پی مکمل یا پی میں نہیں جانا جاتا ہے۔ یہ مسائل (مثال کے طور پر۔ فیکٹرنگ، گراف آئسومورفزم، پیریٹی گیمز) کے مشکل ہونے کا شبہ ہے۔ اسی طرح پی میں ایسے مسائل ہیں جو پی-مکمل یا این سی کے طور پر نہیں جانے جاتے ہیں، لیکن ان کو متوازی بنانا مشکل سمجھا جاتا ہے۔ مثالوں میں دو اعداد کے سب سے بڑے مشترکہ تقسیم کار کو تلاش کرنے کی فیصلہ مسئلہ کی شکلیں شامل ہیں، اس بات کا تعین کرنا کہ دو اعداد دیے جانے پر توسیعی یوکلیڈین الگورتھم کیا جواب دے گا، اور بڑے عدد وزن کے ساتھ گراف کے زیادہ سے زیادہ وزن کے ملاپ کا حساب لگانا۔ نوٹ حوالہ جات گرین لا، ریمنڈ، جیمز ہوور، اور والٹر روزو۔ 1995 میں۔ متوازی حساب کی حدود ؛ پی-مکمل نظریہ۔ ۔ نظریہ تیار کرتا ہے، پھر 96 پی مکمل مسائل کی فہرست بناتا ہے۔ ستورو میاانو، شوجی شیریشی، اور تکایوشی شودائی۔ پی-مکمل مسائل کی فہرست۔ کیوشو یونیورسٹی، RIFIS-TR-CS-17۔ دسمبر 1990۔ پیچیدگی کلاسیں