EXPTIME
کمپیوٹیشنل پیچیدگی کے نظریہ میں، پیچیدگی کی کلاس EXPTIME (جسے بعض اوقات EXP یا DEXPTIME کہا جاتا ہے) ان تمام فیصلہ کن مسائل کا مجموعہ ہے جو ایک تعیناتی ٹورنگ مشین کے ذریعے ایکسپونینشیل وقت میں حل کیے جا سکتے ہیں، یعنی O (2p (n) وقت میں، جہاں p (n) n کا ایک کثیر الجہتی فعل ہے۔ EXPTIME پیچیدگی کی کلاسوں کے ایکسپونینشیل درجہ بندی میں ایک بدیہی کلاس ہے جس میں تیزی سے زیادہ پیچیدہ اوریکلز یا مقداری متبادل ہوتے ہیں۔ مثال کے طور پر، کلاس 2-ایکس پی ٹی آئی ایم ای کی تعریف ایکس پی ٹی آئی ایم ای کی طرح کی گئی ہے لیکن دوگنا ایکسپونینشیل ٹائم باؤنڈ کے ساتھ۔ اسے اعلی اور اعلی وقت کی حدود میں عام کیا جا سکتا ہے۔ EXPTIME کو خلائی کلاس APSPACE کے طور پر بھی تشکیل دیا جا سکتا ہے، جو ان تمام مسائل کا مجموعہ ہے جنہیں کثیر الجہتی جگہ میں متبادل ٹورنگ مشین کے ذریعے حل کیا جا سکتا ہے۔ EXPTIME کا تعلق دیگر بنیادی وقت اور خلائی پیچیدگی کی کلاسوں سے مندرجہ ذیل طریقے سے ہے: P. N. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. P. S. مزید برآں، ٹائم ہیرارکی تھیوریم اور اسپیس ہیرارکی تھیوریم سے یہ معلوم ہوتا ہے کہ پی ایکس پی ٹی آئی ایم ای، این پی ایکس پی ٹی آئی ایم ای اور پی ایس پی اے سی ای ایکس پی ایس پی۔ رسمی تعریف ڈی ٹی آئی ایم ای کے لحاظ سے، دیگر کلاسوں کے ساتھ تعلقات یہ معلوم ہے کہ اور یہ بھی، ٹائم ہیرارکی تھیوریم اور اسپیس ہیرارکی تھیوریم کے مطابق، کہ مذکورہ بالا تاثرات میں، علامت کا مطلب ہے "کا ایک ذیلی سیٹ ہے"، اور علامت کا مطلب ہے "کا ایک سخت ذیلی سیٹ ہے"۔ لہذا پہلے تین میں سے کم از کم ایک شمولیت اور آخری تین میں سے کم از کم ایک شمولیت مناسب ہونی چاہیے، لیکن یہ معلوم نہیں ہے کہ کون سی ہیں۔ زیادہ تر ماہرین کا خیال ہے کہ تمام شمولیت مناسب ہیں۔ یہ بھی معلوم ہے کہ اگر P = NP ہے، تو EXPTIME NEXPTIME، غیر متعین ٹورنگ مشین کے ذریعہ ایکسپونینشیل وقت میں حل ہونے والے مسائل کی کلاس۔ مزید واضح طور پر، EXPTIME § NEXPTIME اگر اور صرف اس صورت میں جب NP میں ایسی شاذ و نادر زبانیں موجود ہوں جو P میں نہ ہوں۔ EXPTIME کو اسپیس کلاس APSPACE کے طور پر دوبارہ تشکیل دیا جا سکتا ہے، جو ان تمام مسائل کا مجموعہ ہے جنہیں کثیر الجہتی جگہ میں متبادل ٹورنگ مشین کے ذریعے حل کیا جا سکتا ہے۔ یہ دیکھنے کا ایک طریقہ ہے کہ پی ایس پی اے سی ای ایکس پی ٹی آئی ایم ای، کیونکہ ایک متبادل ٹورنگ مشین کم از کم اتنی ہی طاقتور ہوتی ہے جتنی کہ ایک متعین ٹورنگ مشین۔ ایکس پی ٹی آئی ایم ای مکمل ایک فیصلہ مسئلہ ایکس پی ٹی آئی ایم ای مکمل ہے اگر یہ ایکس پی ٹی آئی ایم ای میں ہے اور ایکس پی ٹی آئی ایم ای میں ہر مسئلے میں کثیر الجہتی-وقت کئی-ایک کمی ہوتی ہے۔ دوسرے لفظوں میں، ایک کثیر الجہتی وقت کا الگورتھم ہے جو ایک ہی جواب کے ساتھ ایک کی مثالوں کو دوسرے کی مثالوں میں تبدیل کرتا ہے۔ وہ مسائل جو EXPTIME مکمل ہیں انہیں EXPTIME میں سب سے مشکل مسائل کے طور پر سمجھا جا سکتا ہے۔ نوٹ کریں کہ اگرچہ یہ معلوم نہیں ہے کہ آیا NP P کے برابر ہے، لیکن ہم جانتے ہیں کہ EXPTIME-مکمل مسائل P میں نہیں ہیں۔ یہ ثابت ہو چکا ہے کہ ان مسائل کو کثیر الجہتی وقت میں، ٹائم ہیرارکی تھیوریم کے ذریعے حل نہیں کیا جا سکتا۔ کمپیوٹیبلٹی تھیوری میں، بنیادی ناقابل فیصلہ مسائل میں سے ایک رکنے کا مسئلہ ہے: یہ فیصلہ کرنا کہ آیا ایک متعین ٹورنگ مشین (ڈی ٹی ایم) رکتی ہے۔ EXPTIME-مکمل سب سے بنیادی مسائل میں سے ایک اس کا ایک آسان ورژن ہے، جو پوچھتا ہے کہ کیا DTM زیادہ سے زیادہ k مراحل میں دیئے گئے ان پٹ پر رکتا ہے۔ یہ ایکس پی ٹی آئی ایم ای میں ہے کیونکہ ایک معمولی تخروپن کے لیے او (کے) وقت درکار ہوتا ہے، اور ان پٹ کے کو او (لاگ کے) بٹس کا استعمال کرتے ہوئے انکوڈ کیا جاتا ہے جو تخروپن کی تیز رفتار تعداد کا سبب بنتا ہے۔ یہ ایکسپٹیم مکمل ہے کیونکہ، تقریبا بولتے ہوئے، ہم اسے اس بات کا تعین کرنے کے لیے استعمال کر سکتے ہیں کہ آیا ایکسپٹیم مسئلے کو حل کرنے والی مشین کئی مراحل میں قبول کرتی ہے ؛ یہ زیادہ استعمال نہیں کرے گی۔ یونری میں لکھے گئے مراحل کی تعداد کے ساتھ وہی مسئلہ پی-مکمل ہے۔ EXPTIME-مکمل مسائل کی دیگر مثالوں میں عام شطرنج، چیکرز، یا گو (جاپانی کو قوانین کے ساتھ) میں پوزیشن کا اندازہ کرنے کا مسئلہ شامل ہے۔ ان کھیلوں میں ایکس پی ٹی آئی ایم ای مکمل ہونے کا امکان ہوتا ہے کیونکہ کھیل کئی چالوں تک چل سکتے ہیں جو بورڈ کے سائز میں تیزی سے ہوتے ہیں۔ گو کی مثال میں، جاپانی کو اصول ایکسپٹیم مکمل ہونے کا اشارہ کرنے کے لیے جانا جاتا ہے، لیکن یہ معلوم نہیں ہے کہ کھیل کے لیے امریکی یا چینی اصول ایکسپٹیم مکمل ہیں یا نہیں (وہ پی ایس پی اے سی ای سے لے کر ایکسپ اسپیس تک ہو سکتے ہیں)۔ اس کے برعکس، عام کھیل جو بورڈ کے سائز میں کثیر الجہتی متعدد چالوں تک چل سکتے ہیں اکثر پی ایس پی اے سی ای مکمل ہوتے ہیں۔ یہی بات تیزی سے طویل کھیلوں کے بارے میں بھی سچ ہے جس میں غیر تکرار خودکار ہوتی ہے۔ EXPTIME-مکمل مسائل کا ایک اور مجموعہ مختصر سرکٹس سے متعلق ہے۔ سکسینکٹ سرکٹس سادہ مشینیں ہیں جو کچھ گراف کو تیزی سے کم جگہ میں بیان کرنے کے لیے استعمال ہوتی ہیں۔ وہ دو ورٹیکس نمبروں کو ان پٹ اور آؤٹ پٹ کے طور پر قبول کرتے ہیں چاہے ان کے درمیان کوئی کنارہ ہو۔ بہت سے قدرتی P-مکمل گراف کے مسائل کے لیے، جہاں گراف کا اظہار قدرتی نمائندگی جیسے کہ ملحقہ میٹرکس میں کیا جاتا ہے، اسی مسئلے کو ایک مختصر سرکٹ کی نمائندگی پر حل کرنا EXPTIME-مکمل ہے، کیونکہ ان پٹ تیزی سے چھوٹا ہے ؛ لیکن اس کے لیے غیر معمولی ثبوت کی ضرورت ہوتی ہے، کیونکہ مختصر سرکٹس صرف گراف کے ذیلی طبقے کی وضاحت کر سکتے ہیں۔ حوالہ جات پیچیدگی کلاسیں