Sparse language
کمپیوٹیشنل پیچیدگی کے نظریہ میں، ایک غیر معمولی زبان ایک رسمی زبان (تاروں کا ایک مجموعہ) ہے جس میں پیچیدگی فنکشن، زبان میں لمبائی n کے تاروں کی تعداد کو شمار کرتے ہوئے، n کے کثیر الجہتی فنکشن سے منسلک ہوتا ہے۔ وہ بنیادی طور پر دیگر کلاسوں کے ساتھ پیچیدگی کلاس NP کے تعلقات کے مطالعہ میں استعمال ہوتے ہیں۔ تمام غیر معمولی زبانوں کی پیچیدگی کی کلاس کو SPARSE کہا جاتا ہے۔ بکھرے ہوئے زبانوں کو اسپارس کہا جاتا ہے کیونکہ لمبائی n کے کل 2n تار ہوتے ہیں، اور اگر کسی زبان میں صرف کثیر الجہتی طور پر ان میں سے بہت سے ہوتے ہیں، تو اس میں موجود لمبائی n کے تاروں کا تناسب تیزی سے صفر ہو جاتا ہے جیسے جیسے n بڑھتا ہے۔ تمام یونانی زبانیں بہت کم ہیں۔ غیر معمولی غیر معمولی زبان کی ایک مثال بائنری تاروں کا مجموعہ ہے جس میں کچھ فکسڈ k کے لیے بالکل k 1 بٹس ہوتے ہیں۔ ہر n کے لیے، زبان میں صرف تار ہوتے ہیں، جو nk سے جڑے ہوتے ہیں۔ دیگر پیچیدگی کی کلاسوں سے تعلقات SPARSE میں TALLY، یونیری زبانوں کی کلاس شامل ہے، کیونکہ ان میں کسی ایک لمبائی کی زیادہ سے زیادہ ایک تار ہوتی ہے۔ اگرچہ پی/پولی میں تمام زبانیں کم نہیں ہیں، لیکن پی/پولی میں کسی بھی زبان سے ٹورنگ کے کثیر الجہتی وقت میں کمی واقع ہوتی ہے۔ فارچیون نے 1979 میں دکھایا کہ اگر کوئی شاذ و نادر زبان شریک این پی مکمل ہے، تو پی = این پی ؛ مہانے نے 1982 میں یہ ظاہر کرنے کے لیے اس کا استعمال کیا کہ اگر کوئی شاذ و نادر زبان این پی مکمل ہے، تو پی = این پی (یہ مہانے کا نظریہ ہے)۔ لیفٹ سیٹ پر مبنی اس کا ایک آسان ثبوت 1991 میں اوگیہار اور وٹانابے نے دیا تھا۔ مہانے کی دلیل میں حقیقت میں اس بات کی ضرورت نہیں ہے کہ شاذ و نادر زبان این پی میں ہو (کیونکہ این پی-سخت شاذ و نادر سیٹ کے وجود سے این پی-مکمل شاذ و نادر سیٹ کا وجود ظاہر ہوتا ہے)، لہذا ایک شاذ و نادر این پی-سخت سیٹ ہوتا ہے اگر اور صرف اس صورت میں جب پی = این پی ہو۔ مزید برآں، اگر اور صرف اس صورت میں جب این پی میں ایسی شاذ و نادر زبانیں موجود ہوں جو پی میں نہ ہوں۔ ایک این پی مکمل زبان سے ایک شاذ و نادر زبان میں ٹورنگ کی کمی (مہانے کے نظریہ سے کارپ کی کمی کے برخلاف) ہوتی ہے اگر اور صرف اگر۔ 1999 میں، جن-یی کائی اور ڈی سیوکمار نے اوگیہار کے کام کی بنیاد پر یہ ظاہر کیا کہ اگر کوئی غیر معمولی پی-مکمل مسئلہ موجود ہے، تو ایل = پی۔ حوالہ جات بیرونی لنکس لانس فورٹنو۔ پسندیدہ نظریات: چھوٹے سیٹ۔ 18 اپریل 2006۔ ولیم گیسارچ۔ سپارس سیٹس (مہانے کو خراج تحسین)۔ 29 جون، 2007۔ رسمی زبانیں کمپیوٹیشنل پیچیدگی کا نظریہ