Sparse language
கணக்கீட்டு சிக்கலான கோட்பாட்டில், ஒரு சிறிய மொழி என்பது ஒரு முறையான மொழியாகும் (சரங்களின் தொகுப்பு), இது மொழியில் n நீளமுள்ள சரங்களின் எண்ணிக்கையை எண்ணும் சிக்கலான செயல்பாடு, n இன் பல்லுறுப்புக்கோவை செயல்பாட்டால் வரையறுக்கப்படுகிறது. அவை முதன்மையாக மற்ற வகுப்புகளுடன் சிக்கலான வகுப்பு NP இன் உறவைப் பற்றிய ஆய்வில் பயன்படுத்தப்படுகின்றன. அனைத்து அரிதான மொழிகளின் சிக்கலான வகை SPARSE என்று அழைக்கப்படுகிறது. மொத்தமாக n நீளமுள்ள 2n சரங்கள் இருப்பதால் அரிதான மொழிகள் ஸ்பார்ஸ் என்று அழைக்கப்படுகின்றன, மேலும் ஒரு மொழியில் பல்லுறுப்புக்கோவை ரீதியாக இவை பல இருந்தால், n வளரும்போது அதில் உள்ள n நீளமுள்ள சரங்களின் விகிதம் விரைவாக பூஜ்ஜியத்திற்குச் செல்லும். அனைத்து யூனரி மொழிகளும் அரிதானவை. ஒரு அற்பமான குறைவான மொழிக்கு ஒரு எடுத்துக்காட்டு சில நிலையான k க்கு சரியாக k 1 பிட்களைக் கொண்ட பைனரி சரங்களின் தொகுப்பாகும்; ஒவ்வொரு n க்கும், மொழியில் சரங்கள் மட்டுமே உள்ளன, அவை nk ஆல் வரையறுக்கப்பட்டுள்ளன. மற்ற சிக்கலான வகுப்புகளுடனான உறவுகள் SPARSE இல் TALLY, யூனரி மொழிகளின் வகுப்பைக் கொண்டுள்ளது, ஏனெனில் இவை எந்த ஒரு நீளத்தின் அதிகபட்ச ஒரு சரத்தைக் கொண்டுள்ளன. பி/பாலியில் உள்ள அனைத்து மொழிகளும் குறைவாக இல்லை என்றாலும், பி/பாலியில் உள்ள எந்த மொழியிலிருந்தும் ஒரு பல்லுறுப்புக்கோவை-நேர டூரிங் குறைப்பு உள்ளது. 1979 ஆம் ஆண்டில் ஃபார்ச்சூன் காட்டியது என்னவென்றால், எந்தவொரு சிறிய மொழியும் இணை-என். பி-முழுமையடைந்தால், பி = என். பி.; மகனே இதைப் பயன்படுத்தி 1982 ஆம் ஆண்டில் எந்த ஒரு சிறிய மொழியும் என். பி-முழுமையடைந்தால், பி = என். பி. (இது மகனேயின் தேற்றம்) என்று காட்டினார். இதற்கு ஒரு எளிய சான்றை 1991 ஆம் ஆண்டில் ஓகிஹாரா மற்றும் வதனாபே ஆகியோர் லெஃப்ட் செட்களை அடிப்படையாகக் கொண்டு வழங்கினர். மகனேயின் வாதம் உண்மையில் குறுகிய மொழி NP இல் இருக்க வேண்டிய அவசியமில்லை (ஏனெனில் ஒரு NP-கடினமான விரிந்த தொகுப்பின் இருப்பு ஒரு NP-முழுமையான விரிந்த தொகுப்பின் இருப்பைக் குறிக்கிறது), எனவே P = NP என்றால் மட்டுமே ஒரு சிறிய NP-கடினமான தொகுப்பு உள்ளது. மேலும், P இல் இல்லாத NP இல் அரிதான மொழிகள் இருந்தால் மட்டுமே E § NE. ஒரு NP-முழுமையான மொழியிலிருந்து ஒரு அரிதான மொழிக்கு ஒரு டூரிங் குறைப்பு (மகாநியின் தேற்றத்திலிருந்து கார்ப் குறைப்புக்கு மாறாக) இருந்தால் மட்டுமே. 1999 ஆம் ஆண்டில், ஜின்-யி கை மற்றும் டி. சிவகுமார், ஒகிஹாராவின் பணியை அடிப்படையாகக் கொண்டு, ஒரு சிறிய பி-முழுமையான சிக்கல் இருந்தால், எல் = பி. குறிப்புகள் வெளிப்புற இணைப்புகள் லான்ஸ் ஃபோர்ட்னோ. பிடித்த கோட்பாடுகள்ஃ சிறிய தொகுப்புகள். ஏப்ரல் 18,2006. வில்லியம் கஸார்ச். ஸ்பார்ஸ் செட்ஸ் (மகனேவுக்கு அஞ்சலி). ஜூன் 29,2007. முறையான மொழிகள் கணக்கீட்டு சிக்கல் கோட்பாடு