Unary language
கணக்கீட்டு சிக்கலான கோட்பாட்டில், ஒரு யூனரி மொழி அல்லது டாலி மொழி என்பது ஒரு முறையான மொழியாகும் (சரங்களின் தொகுப்பு) இதில் அனைத்து சரங்களும் 1k வடிவத்தைக் கொண்டுள்ளன, இதில் "1" எந்த நிலையான சின்னமாகவும் இருக்கலாம். எடுத்துக்காட்டாக, மொழி {1,111,1111} யூனரி ஆகும், அதே போல் மொழி {1k | k என்பது பகா எண்} ஆகும். அத்தகைய அனைத்து மொழிகளின் சிக்கலான வகுப்பும் சில நேரங்களில் டாலி என்று அழைக்கப்படுகிறது. யூனரி மொழி என்பது யூனரி எண் அமைப்பில் இயற்கையான எண்களின் தொகுப்பின் குறியாக்கம் என்பதிலிருந்து "யூனரி" என்ற பெயர் வருகிறது. எந்தவொரு வரையறுக்கப்பட்ட எழுத்துக்களிலும் சரங்களின் பிரபஞ்சம் ஒரு கணக்கிடக்கூடிய தொகுப்பாக இருப்பதால், ஒவ்வொரு மொழியையும் இயற்கையான எண்களின் தனித்துவமான தொகுப்பாக வரைபடமாக்க முடியும்; எனவே, ஒவ்வொரு மொழியும் ஒரு ஒற்றை பதிப்பு {A இல் 1k | 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 பி/பாலியில் உள்ளது-உள்ளீட்டு நீளத்தை மட்டுமே சார்ந்திருக்கும் ஒரு ஆலோசனை செயல்பாட்டைக் கொடுக்கப்பட்ட பல்லுறுப்புக்கோவை நேரத்தில் அடையாளம் காணக்கூடிய மொழிகளின் வகுப்பு. இந்த வழக்கில், தேவையான ஆலோசனை செயல்பாடு மிகவும் எளிதானது-இது 1k மொழியில் உள்ளதா இல்லையா என்பதைக் குறிப்பிடும் ஒவ்வொரு உள்ளீட்டு நீளத்திற்கும் ஒரு பிட்டைத் தருகிறது. ஒரு யூனரி மொழி என்பது ஒரு சிறிய மொழியாகும், ஏனெனில் ஒவ்வொரு n க்கும் இது அதிகபட்சம் n நீளத்தின் ஒரு மதிப்பையும் அதிகபட்சம் n நீளத்தின் n மதிப்புகளையும் கொண்டுள்ளது, ஆனால் அனைத்து சிறிய மொழிகளும் யூனரி அல்ல; எனவே TALLY என்பது SPARSE இல் உள்ளது. NP-கடினமான யூனரி மொழிகள் இல்லை என்று நம்பப்படுகிறதுஃ NP-முழுமையான ஒரு யூனரி மொழி இருந்தால், P = NP. இதன் விளைவாக அரிதான மொழிகளுக்கு விரிவுபடுத்தப்படலாம். எல் ஒரு யூனரி மொழியாக இருந்தால், எல் * (எல் இன் க்ளீன் நட்சத்திரம்) ஒரு வழக்கமான மொழியாகும். டாலி வகுப்புகள் சிக்கலான வகுப்பு P1 என்பது யூனரி மொழிகளின் வகுப்பாகும், இது ஒரு பல்லுறுப்புக்கோவை நேர டூரிங் இயந்திரத்தால் அடையாளம் காண முடியும் (அதன் உள்ளீடு யூனரியில் எழுதப்பட்டுள்ளது); இது வகுப்பு P இன் அனலாக் ஆகும். ஒரு எண்ணும் வகுப்பு #P 1, #P இன் அனலாக், மேலும் அறியப்படுகிறது. குறிப்புகள் குறிப்புகள் பொது குறிப்புகள் லான்ஸ் ஃபோர்ட்னோ. பிடித்த கோட்பாடுகள்ஃ சிறிய தொகுப்புகள். ஏப்ரல் 18,2006. முறையான மொழிகள் கணக்கீட்டு சிக்கல் கோட்பாடு