Unary language
کمپیوٹیشنل پیچیدگی کے نظریہ میں، ایک یونیری زبان یا ٹیلی زبان ایک رسمی زبان (تاروں کا ایک مجموعہ) ہے جہاں تمام تاروں کی شکل 1k ہوتی ہے، جہاں "1" کوئی بھی فکسڈ علامت ہو سکتی ہے۔ مثال کے طور پر، زبان {1,111,1111} یونیری ہے، جیسا کہ زبان {1k | k پرائم ہے} ہے۔ ایسی تمام زبانوں کی پیچیدگی کی کلاس کو بعض اوقات TALLY کہا جاتا ہے۔ نام "یونیری" اس حقیقت سے آیا ہے کہ یونیری زبان یونیری عددی نظام میں قدرتی اعداد کے ایک سیٹ کی انکوڈنگ ہے۔ چونکہ کسی بھی محدود حروف تہجی پر تاروں کی کائنات ایک قابل شمار سیٹ ہے، اس لیے ہر زبان کو قدرتی اعداد کے ایک منفرد سیٹ A میں نقشہ بنایا جا سکتا ہے ؛ اس طرح، ہر زبان کا ایک یونیری ورژن {A میں 1k | k} ہوتا ہے۔ اس کے برعکس، ہر یونیری زبان کا ایک زیادہ کمپیکٹ بائنری ورژن ہوتا ہے، قدرتی اعداد k کے بائنری انکوڈنگ کا مجموعہ اس طرح ہے کہ 1k زبان میں ہے۔ چونکہ پیچیدگی کو عام طور پر ان پٹ سٹرنگ کی لمبائی کے لحاظ سے ماپا جاتا ہے، اس لیے کسی زبان کا یونیری ورژن اصل زبان سے "آسان" ہو سکتا ہے۔ مثال کے طور پر، اگر کسی زبان کو O (2n) وقت میں پہچانا جا سکتا ہے، تو اس کے یونیری ورژن کو O (n) وقت میں پہچانا جا سکتا ہے، کیونکہ n تیزی سے بڑا ہو گیا ہے۔ زیادہ عام طور پر، اگر کسی زبان کو O (f (n)) وقت اور O (g (n)) جگہ میں پہچانا جا سکتا ہے، تو اس کے یونیری ورژن کو O (n + f (log n)) وقت اور O (g (log n) جگہ میں پہچانا جا سکتا ہے (ہمیں صرف ان پٹ سٹرنگ کو پڑھنے کے لیے O (n) وقت درکار ہوتا ہے)۔ تاہم، اگر کسی زبان میں رکنیت ناقابل فیصلہ ہے، تو اس کے غیر متزلزل ورژن میں رکنیت بھی ناقابل فیصلہ ہے۔ دیگر پیچیدگی کی کلاسوں سے تعلقات TALLY P/پولی میں موجود ہے-زبانوں کی وہ کلاس جسے کثیر الجہتی وقت میں پہچانا جا سکتا ہے جس میں ایک مشاورتی فنکشن دیا جاتا ہے جو صرف ان پٹ کی لمبائی پر منحصر ہوتا ہے۔ اس صورت میں، مطلوبہ مشورے کا فنکشن بہت آسان ہے-یہ ہر ان پٹ لمبائی k کے لیے ایک بٹ واپس کرتا ہے جس میں یہ واضح کیا جاتا ہے کہ 1k زبان میں ہے یا نہیں۔ ایک یونیری زبان لازمی طور پر ایک غیر معمولی زبان ہے، کیونکہ ہر n کے لیے اس کی لمبائی n کی زیادہ سے زیادہ ایک قدر ہوتی ہے اور زیادہ سے زیادہ n کی لمبائی کی زیادہ سے زیادہ n اقدار ہوتی ہیں، لیکن تمام غیر معمولی زبانیں یونیری نہیں ہوتیں۔ اس طرح TALLY SPARSE میں موجود ہے۔ یہ خیال کیا جاتا ہے کہ کوئی این پی ہارڈ یونری زبانیں موجود نہیں ہیں: اگر کوئی یونری زبان موجود ہے جو این پی مکمل ہے، تو پی = این پی۔ اس نتیجے کو کم زبانوں تک بڑھایا جا سکتا ہے۔ اگر L ایک واحد زبان ہے، تو L * (L کا کلین اسٹار) ایک باقاعدہ زبان ہے۔ ٹیلی کلاسیں پیچیدگی کلاس P1 یونیری زبانوں کی وہ کلاس ہے جسے کثیر الجہتی ٹائم ٹورنگ مشین کے ذریعے پہچانا جا سکتا ہے (اس کے ان پٹ کو یونیری میں لکھا گیا ہے) ؛ یہ کلاس P کا ینالاگ ہے۔ یونیری ترتیب میں NP کا ینالاگ NP1 ہے۔ ایک گنتی کلاس #P 1، #P کا ینالاگ بھی جانا جاتا ہے۔ حوالہ جات نوٹس جنرل حوالہ جات لانس فورٹنو۔ پسندیدہ نظریات: چھوٹے سیٹ۔ 18 اپریل 2006۔ رسمی زبانیں کمپیوٹیشنل پیچیدگی کا نظریہ