Structural complexity theory
கணினி அறிவியலின் கணக்கீட்டு சிக்கலான கோட்பாட்டில், கட்டமைப்பு சிக்கலான கோட்பாடு அல்லது வெறுமனே கட்டமைப்பு சிக்கலானது தனிப்பட்ட சிக்கல்கள் மற்றும் வழிமுறைகளின் கணக்கீட்டு சிக்கலான தன்மையை விட சிக்கலான வகுப்புகளின் ஆய்வு ஆகும். இது பல்வேறு சிக்கலான வகுப்புகளின் உள் கட்டமைப்புகள் மற்றும் வெவ்வேறு சிக்கலான வகுப்புகளுக்கு இடையிலான உறவுகள் ஆகிய இரண்டின் ஆராய்ச்சியையும் உள்ளடக்கியது. இந்த வகையான முதல் மற்றும் இன்னும் மிக முக்கியமான கேள்வியான பி = என். பி. சிக்கலைத் தீர்ப்பதற்கான (இன்னும் தோல்வியுற்ற) முயற்சிகளின் விளைவாக இந்தக் கோட்பாடு உருவாகியுள்ளது. பெரும்பாலான ஆராய்ச்சிகள் பி என்பிக்கு சமமாக இல்லை என்ற அனுமானத்தின் அடிப்படையிலும், சிக்கலான வகுப்புகளின் பல்லுறுப்புக்கோவை நேர வரிசைமுறை எல்லையற்றது என்ற தொலைநோக்கு அனுமானத்தின் அடிப்படையிலும் செய்யப்படுகின்றன. முக்கியமான முடிவுகள் சுருக்கத் தேற்றம் சுருக்கத் தேற்றம் என்பது கணக்கிடக்கூடிய செயல்பாடுகளின் சிக்கலைப் பற்றிய ஒரு முக்கியமான தேற்றமாகும். அனைத்து கணக்கிடக்கூடிய செயல்பாடுகளையும் கொண்ட கணக்கிடக்கூடிய எல்லையுடன் மிகப்பெரிய சிக்கலான வகுப்பு இல்லை என்று தேற்றம் கூறுகிறது. விண்வெளி படிநிலைக் கோட்பாடுகள் விண்வெளி படிநிலைக் கோட்பாடுகள் என்பது பிரிப்பு முடிவுகளாகும், அவை சில நிபந்தனைகளுக்கு உட்பட்டு, அதிக இடத்தில் (அறிகுறியற்ற முறையில்) அதிக சிக்கல்களைத் தீர்க்க முடியும் என்பதைக் காட்டுகின்றன. எடுத்துக்காட்டாக, ஒரு தீர்மானகரமான டூரிங் இயந்திரம் ஸ்பேஸ் n ஐ விட ஸ்பேஸ் n பதிவு n இல் அதிக முடிவு சிக்கல்களை தீர்க்க முடியும். நேரத்திற்கான சற்றே பலவீனமான ஒத்த கோட்பாடுகள் நேர படிநிலை கோட்பாடுகளாகும். நேர வரிசைமுறை கோட்பாடுகள் நேர வரிசைமுறை கோட்பாடுகள் டூரிங் இயந்திரங்களில் நேர வரம்புக்குட்பட்ட கணக்கீடு பற்றிய முக்கியமான அறிக்கைகள் ஆகும். முறைசாரா முறையில், இந்த கோட்பாடுகள் அதிக நேரம் கொடுக்கப்பட்டால், ஒரு டூரிங் இயந்திரம் அதிக சிக்கல்களை தீர்க்க முடியும் என்று கூறுகின்றன. எடுத்துக்காட்டாக, n2 நேரத்துடன் தீர்க்கக்கூடிய சிக்கல்கள் உள்ளன, ஆனால் n நேரத்துடன் அல்ல. வாலியன்ட்-வஜீரானி தேற்றம் என்பது கணக்கீட்டு சிக்கல் கோட்பாட்டில் ஒரு தேற்றம் ஆகும். 1986 இல் வெளியிடப்பட்ட தனித்துவமான தீர்வுகளைக் கண்டறிவது போல் NP எளிதானது என்ற தலைப்பில் லெஸ்லி வாலியன்ட் மற்றும் விஜய் வஜிராணி ஆகியோர் தங்கள் கட்டுரையில் நிரூபித்தனர். சந்தேகத்திற்கு இடமில்லாத-SAT க்கு ஒரு பல்லுறுப்புக்கோவை நேர வழிமுறை இருந்தால், NP = RP என்று தேற்றம் கூறுகிறது. ஆதாரம் முல்முலி-வஜிரானி தனிமைப்படுத்தப்பட்ட லெம்மாவை அடிப்படையாகக் கொண்டது, இது பின்னர் கோட்பாட்டு கணினி அறிவியலில் பல முக்கியமான பயன்பாடுகளுக்கு பயன்படுத்தப்பட்டது. சிப்சர்-லாட்மேன் தேற்றம் சிப்சர்-லாட்மேன் தேற்றம் அல்லது சிப்சர்-காக்ஸ்-லாட்மேன் தேற்றம், எல்லைக்குட்பட்ட-பிழை நிகழ்தகவு பல்லுறுப்புக்கோவை (பிபிபி) நேரம், பல்லுறுப்புக்கோவை நேர வரிசைமுறையில் உள்ளது, மேலும் குறிப்பாக σ2 θ Π2. 1970 ஆம் ஆண்டில் வால்டர் சாவிட்ச் நிரூபித்த சாவிட்சின் தேற்றம், தீர்மானகரமான மற்றும் தீர்மானிக்கப்படாத விண்வெளி சிக்கலுக்கு இடையிலான உறவை வழங்குகிறது. எந்தவொரு செயல்பாட்டிற்கும், தோதாவின் தேற்றம் என்பது சீனோசூக் தோடா தனது ஆய்வறிக்கையான "பிபி என்பது பல்லுறுப்புக்கோவை-நேர படிநிலையைப் போல கடினமானது" (1991) இல் நிரூபிக்கப்பட்ட ஒரு விளைவாகும் என்று அது கூறுகிறது, மேலும் 1998 கோடல் பரிசு வழங்கப்பட்டது. முழு பல்லுறுப்புக்கோவை படிநிலை PH PPP இல் உள்ளது என்று தேற்றம் கூறுகிறது; இது ஒரு நெருக்கமான தொடர்புடைய அறிக்கையைக் குறிக்கிறது, PH P#P இல் உள்ளது. இம்மர்மேன்-செலெப்செனி தேற்றம் 1987 ஆம் ஆண்டில் நீல் இம்மர்மேன் மற்றும் ராபர்ட் செலெப்செனி ஆகியோரால் சுயாதீனமாக நிரூபிக்கப்பட்டது, இதற்காக அவர்கள் 1995 கோடல் பரிசைப் பகிர்ந்து கொண்டனர். அதன் பொதுவான வடிவத்தில், எந்தவொரு செயல்பாட்டிற்கும் NSPACE (s (n)) = கோ-NSPACE (s (n)) என்று தேற்றம் கூறுகிறது. முடிவு சமமாக என்எல் = கோ-என்எல் என குறிப்பிடப்படுகிறது. இது எஸ் (என்) = லாக் என் போது சிறப்பு வழக்கு என்றாலும், இது ஒரு நிலையான திணிப்பு வாதத்தால் பொதுவான தேற்றத்தைக் குறிக்கிறது. இதன் விளைவாக இரண்டாவது எல். பி. ஏ சிக்கல் தீர்க்கப்பட்டது. ஆராய்ச்சி தலைப்புகள் இந்த பகுதியில் ஆராய்ச்சியின் முக்கிய திசைகள் பின்வருமாறுஃ சிக்கலான வகுப்புகள் பற்றிய பல்வேறு தீர்க்கப்படாத சிக்கல்களிலிருந்து எழும் தாக்கங்கள் பற்றிய ஆய்வு, பல்வேறு வகையான வள-கட்டுப்படுத்தப்பட்ட குறைப்புகளின் ஆய்வு மற்றும் சேமிப்பு மற்றும் தரவு குறிப்புகளுக்கான அணுகல் ஆகியவற்றின் வழிமுறைகள் மற்றும் பல்வேறு கட்டுப்பாடுகளின் விளைவுகள் குறித்த முழுமையான மொழிகள் ஆய்வு.