LP-type problem
வழிமுறைகளின் ஆய்வில், ஒரு LP-வகை சிக்கல் (ஒரு பொதுமைப்படுத்தப்பட்ட நேரியல் நிரல் என்றும் அழைக்கப்படுகிறது) என்பது ஒரு உகப்பாக்கம் சிக்கலாகும், இது குறைந்த பரிமாண நேரியல் நிரல்களுடன் சில பண்புகளைப் பகிர்ந்து கொள்கிறது, மேலும் இது ஒத்த வழிமுறைகளால் தீர்க்கப்படலாம். LP-வகை சிக்கல்களில் பல முக்கியமான உகப்பாக்கம் சிக்கல்கள் அடங்கும், அவை நேரியல் நிரல்கள் அல்ல, அதாவது கொடுக்கப்பட்ட பிளானர் புள்ளிகளைக் கொண்ட மிகச்சிறிய வட்டத்தைக் கண்டுபிடிப்பதில் உள்ள சிக்கல் போன்றவை. சீரற்ற வழிமுறைகளின் கலவையால் அவை தீர்க்கப்படலாம், இது சிக்கலை வரையறுக்கும் கூறுகளின் எண்ணிக்கையில் நேரியல் மற்றும் சிக்கலின் பரிமாணத்தில் சப்எக்ஸ்போனென்ஷியல் ஆகும். வரையறை எல்பி-வகை சிக்கல்கள் வரையறுக்கப்பட்டன, இதில் உள்ளீடு ஒரு வரையறுக்கப்பட்ட உறுப்புகளின் தொகுப்பாக வழங்கப்படுகிறது, மேலும் முற்றிலும் வரிசைப்படுத்தப்பட்ட தொகுப்பிலிருந்து மதிப்புகளுக்கு துணைக்குழுக்களை வரைபடமாக்கும் செயல்பாடு. இரண்டு முக்கிய பண்புகளை பூர்த்தி செய்ய செயல்பாடு தேவைப்படுகிறதுஃ மோனோடோனிசிட்டிஃ ஒவ்வொரு இரண்டு செட்களுக்கும், f (A) ≤ f (B) ≤ f (S). இருப்பிடம்ஃ ஒவ்வொரு இரண்டு செட்களுக்கும், ஒவ்வொரு உறுப்புக்கும், என்றால், பின்னர். ஒரு LP-வகை சிக்கலின் அடிப்படை என்பது ஒவ்வொரு சரியான துணைக்குழுவும் தன்னை விட சிறிய மதிப்பைக் கொண்டிருக்கும் பண்பைக் கொண்ட ஒரு தொகுப்பாகும், மேலும் ஒரு LP-வகை சிக்கலின் பரிமாணம் (அல்லது ஒருங்கிணைந்த பரிமாணம்) ஒரு அடிப்படையின் அதிகபட்ச கார்டினாலிட்டி என்று வரையறுக்கப்படுகிறது. ஒரு ஆப்டிமைசேஷன் அல்காரிதம் ஒரு அடிப்படையில் ஒரு உறுப்பைச் சேர்ப்பதன் மூலம் உருவாக்கப்பட்ட செட்களில் மட்டுமே செயல்பாட்டை மதிப்பீடு செய்ய முடியும் என்று கருதப்படுகிறது. மாற்றாக, வழிமுறை இரண்டு பழமையான செயல்பாடுகளுக்கு மட்டுப்படுத்தப்படலாம்ஃ ஒரு அடிப்படை மற்றும் ஒரு உறுப்புக்கு என்பதை தீர்மானிக்கும் ஒரு மீறல் சோதனை, மற்றும் ஒரு அடிப்படை கணக்கீடு (அதே உள்ளீடுகளுடன்) ஒரு அடிப்படையைக் கண்டறிகிறது. இந்த கட்டுப்படுத்தப்பட்ட மதிப்பீடுகள் அல்லது முதன்மையானவற்றை மட்டுமே பயன்படுத்துவதன் மூலம் மதிப்பீடு செய்வதே வழிமுறையின் பணியாகும். எடுத்துக்காட்டுகள் மற்றும் பயன்பாடுகள் ஒரு நேரியல் நிரல் எதிர்மறை அல்லாத உண்மையான மாறிகளின் அமைப்பால் வரையறுக்கப்படலாம், நேரியல் சமத்துவமின்மை கட்டுப்பாடுகளுக்கு உட்பட்டு, குறைக்கப்பட வேண்டிய எதிர்மறை அல்லாத நேரியல் புறநிலை செயல்பாட்டுடன். கட்டுப்பாடுகளின் தொகுப்பாக இருக்க அனுமதிப்பதன் மூலமும், வரையறுக்கப்பட்ட சிறிய நேரியல் நிரலின் குறைந்தபட்ச புறநிலை செயல்பாட்டு மதிப்பாக (கட்டுப்பாடுகளின் துணைக்குழுவிற்கு) வரையறுப்பதன் மூலமும் இது LP-வகை சிக்கல்களின் கட்டமைப்பிற்குள் வைக்கப்படலாம். பொருத்தமான பொது நிலை அனுமானங்களுடன் (ஒரே உகந்த புறநிலை செயல்பாட்டு மதிப்பைக் கொண்ட பல தீர்வு புள்ளிகளைத் தடுப்பதற்காக), இது ஒரு எல்பி-வகை சிக்கலின் மோனோடோனிசிட்டி மற்றும் இருப்பிடத் தேவைகளைப் பூர்த்தி செய்கிறது, மேலும் மாறிகளின் எண்ணிக்கைக்கு சமமான ஒருங்கிணைந்த பரிமாணத்தைக் கொண்டுள்ளது. இதேபோல், ஒரு முழு எண் நிரல் (ஒரு நேரியல் நிரலைப் போலவே நேரியல் கட்டுப்பாடுகளின் தொகுப்பு மற்றும் ஒரு நேரியல் புறநிலை செயல்பாட்டைக் கொண்டுள்ளது, ஆனால் மாறிகள் முழு எண் மதிப்புகளை மட்டுமே எடுக்க வேண்டும் என்ற கூடுதல் கட்டுப்பாட்டுடன்) ஒரு LP-வகை சிக்கலின் மோனோடோனிசிட்டி மற்றும் வட்டார பண்புகள் இரண்டையும் திருப்திப்படுத்துகிறது, நேரியல் நிரல்களுக்கான அதே பொதுவான நிலை அனுமானங்களுடன். இன் கோட்பாடுகள் மற்றும், மாறிகள் கொண்ட ஒரு முழு எண் நிரலுக்கு, ஒருங்கிணைந்த பரிமாணம் அதிகபட்சமாக உள்ளது என்பதைக் காட்டுகிறது. கணக்கீட்டு வடிவவியலில் பல இயற்கையான உகப்பாக்கம் சிக்கல்கள் எல்பி-வகை ஆகும்ஃ சிறிய வட்ட சிக்கல் என்பது ஒரு வட்டத்தின் குறைந்தபட்ச ஆரத்தைக் கண்டுபிடிப்பதில் உள்ள சிக்கலாகும். இது மோனோடோனிசிட்டி (அதிக புள்ளிகளைச் சேர்ப்பது வட்டத்தை பெரியதாக மட்டுமே மாற்றும்) மற்றும் இருப்பிடத்தை (தொகுப்புக்கான மிகச்சிறிய வட்டத்தில் இருந்தால், அதே வட்டமும் இருந்தால்) திருப்திப்படுத்துகிறது. மிகச்சிறிய வட்டம் எப்போதும் சில மூன்று புள்ளிகளால் தீர்மானிக்கப்படுவதால், மிகச்சிறிய வட்டம் சிக்கல் இரு பரிமாண யூக்ளிடியன் வடிவவியலைப் பயன்படுத்தி வரையறுக்கப்பட்டாலும், ஒருங்கிணைந்த பரிமாணம் மூன்றைக் கொண்டுள்ளது. மேலும் பொதுவாக, பரிமாணங்களில் புள்ளிகளின் மிகச்சிறிய மூடப்பட்ட பந்து ஒருங்கிணைந்த பரிமாணத்தின் எல்பி-வகை சிக்கலை உருவாக்குகிறது. மிகச்சிறிய வட்டம் சிக்கலை பந்துகளின் தொகுப்பைச் சுற்றியுள்ள மிகச்சிறிய பந்து, பந்துகளின் தொகுப்பைத் தொடும் அல்லது சுற்றியுள்ள மிகச்சிறிய பந்து, எடையுள்ள 1-சென்டர் சிக்கல் அல்லது யூக்ளிடியன் அல்லாத இடங்களில் இதே போன்ற சிறிய பந்து சிக்கல்களுக்கு பொதுமைப்படுத்தலாம். மிகச்சிறிய மூடப்பட்ட நீள்வட்டத்தைக் கண்டுபிடிப்பதில் தொடர்புடைய சிக்கல் ஒரு எல்பி-வகை சிக்கலாகும், ஆனால் ஒரு பெரிய ஒருங்கிணைந்த பரிமாணத்துடன்,. - பரிமாண யூக்ளிடியன் இடத்தில் குவிந்த தொகுப்புகளின் வரிசையாக இருக்கட்டும், மேலும் ஒரு பொதுவான குறுக்குவெட்டு புள்ளியைக் கொண்ட இந்த வரிசையின் மிக நீளமான முன்னொட்டு கண்டுபிடிக்க விரும்புகிறோம் என்று வைத்துக்கொள்வோம். இது ஒரு LP-வகை சிக்கலாக வெளிப்படுத்தப்படலாம், இதில் கி என்பது A இன் முதல் உறுப்பினர், இது A இன் குறுக்குவெட்டு முன்னொட்டுக்கு சொந்தமானது அல்ல, அத்தகைய உறுப்பினர் இல்லையென்றால். இந்த அமைப்பின் ஒருங்கிணைந்த பரிமாணம். முப்பரிமாண இடத்தில் அச்சு-சீரமைக்கப்பட்ட செவ்வக பெட்டிகளின் தொகுப்பு நமக்கு வழங்கப்பட்டுள்ளது என்று வைத்துக்கொள்வோம், மேலும் அனைத்து பெட்டிகளையும் வெட்டுகின்ற இடத்தின் நேர்மறை ஆக்டான்ட்டுக்குள் ஒரு கோட்டைக் கண்டுபிடிக்க விரும்புகிறோம். இது ஒருங்கிணைந்த பரிமாணம் 4 உடன் ஒரு LP-வகை சிக்கலாக வெளிப்படுத்தப்படலாம். இரண்டு குவிந்த பாலிட்டோப்புகளுக்கு இடையிலான மிக நெருக்கமான தூரத்தைக் கண்டுபிடிப்பதில் உள்ள சிக்கல், அவற்றின் செங்குத்துகளின் தொகுப்புகளால் குறிப்பிடப்படுகிறது, இது ஒரு LP-வகை சிக்கலாக குறிப்பிடப்படலாம். இந்த சூத்திரத்தில், செட் என்பது இரண்டு பாலிடோப்புகளிலும் உள்ள அனைத்து செங்குத்துகளின் தொகுப்பாகும், மேலும் செயல்பாட்டு மதிப்பு என்பது இரண்டு பாலிடோப்புகளில் உள்ள செங்குத்துகளின் இரண்டு துணைக்குழுக்களின் குவிந்த மேலோட்டங்களுக்கு இடையிலான மிகச்சிறிய தூரத்தின் எதிர்மறையாகும். சிக்கலின் ஒருங்கிணைந்த பரிமாணம் என்னவென்றால், இரண்டு பாலிட்டோப்புகளும் ஒன்றோடொன்று வேறுபட்டிருந்தால், அல்லது அவை காலியாக இல்லாத குறுக்குவெட்டைக் கொண்டிருந்தால். குவாசிகோன்வெக்ஸ் செயல்பாடுகளின் தொகுப்பாக இருக்கட்டும். பின்னர் புள்ளி வாரியாக அதிகபட்சம் குவாசிகோன்வெக்ஸ் ஆகும், மேலும் குறைந்தபட்ச மதிப்பைக் கண்டுபிடிப்பதில் உள்ள சிக்கல் ஒரு LP-வகை சிக்கலாகும். இது அதிகபட்சமாக ஒருங்கிணைந்த பரிமாணத்தைக் கொண்டுள்ளது, செயல்பாடுகளின் களத்தின் பரிமாணம் எங்கே, ஆனால் போதுமான மென்மையான செயல்பாடுகளுக்கு ஒருங்கிணைந்த பரிமாணம் சிறியது, அதிகபட்சம். குவாசிகோன்வெக்ஸ் செயல்பாடுகளைப் பயன்படுத்தி பல எல். பி-வகை சிக்கல்களையும் இந்த வழியில் வெளிப்படுத்தலாம்; எடுத்துக்காட்டாக, கொடுக்கப்பட்ட புள்ளிகளில் ஒன்றிலிருந்து யூக்ளிடியன் தூரத்தை ஒவ்வொரு செயல்பாடும் அளவிடும் இடத்தில் குறைக்கும் சிக்கல் மிகச்சிறிய வலையமைப்பு சிக்கலாகும். வழிமுறை விளையாட்டு கோட்பாட்டில் சில விளையாட்டுகளின் உகந்த விளைவுகளைத் தீர்மானிக்கவும், வரையறுக்கப்பட்ட உறுப்பு முறை மெஷ்களில் வெர்டெக்ஸ் பிளேஸ்மென்ட்டை மேம்படுத்தவும், வசதி இருப்பிட சிக்கல்களைத் தீர்க்கவும், சில அதிவேக-நேர தேடல் வழிமுறைகளின் நேர சிக்கலை பகுப்பாய்வு செய்யவும், அவற்றின் இரு பரிமாணப் படங்களிலிருந்து பொருட்களின் முப்பரிமாண நிலைகளை மறுகட்டமைக்கவும் எல்பி-வகை சிக்கல்கள் பயன்படுத்தப்பட்டுள்ளன. படிமுறைகள் சீடெல் குறைந்த பரிமாண நேரியல் நிரலாக்கத்திற்கான ஒரு வழிமுறையை வழங்கியது, இது LP-வகை சிக்கல் கட்டமைப்பிற்கு ஏற்ப மாற்றியமைக்கப்படலாம். சீடலின் வழிமுறை தொகுப்பை உள்ளீடாகவும், உகந்த அடிப்படையைச் சேர்ந்ததாக அறியப்பட்ட கூறுகளின் தனி தொகுப்பாகவும் (ஆரம்பத்தில் காலியாக) எடுத்துக்கொள்கிறது. இது பின்னர் மீதமுள்ள கூறுகளை ஒரு சீரற்ற வரிசையில் ஒவ்வொன்றாக பரிசீலித்து, ஒவ்வொன்றிற்கும் மீறல் சோதனைகளைச் செய்து, முடிவைப் பொறுத்து, அறியப்பட்ட அடிப்படை கூறுகளின் பெரிய தொகுப்புடன் அதே வழிமுறையை மீண்டும் மீண்டும் அழைக்கிறது. இது பின்வரும் போலி குறியீட்டைக் கொண்டு வெளிப்படுத்தப்படலாம்ஃ செயல்பாடு சீடல் (S, f, X) என்பது R: = வெற்று தொகுப்பு B: = S இன் சீரற்ற வரிசைமாற்றத்தில் x க்கான X: f (B) §f (B ≤ {x}): B: = சீடல் (R, f, X ≤ {x}) R: = R ≤ {x} திரும்பும் B ஒருங்கிணைந்த பரிமாணத்துடன் ஒரு சிக்கலில், வழிமுறை மீறல் சோதனை மீதமுள்ள அடிப்படை கூறுகளில் ஒன்றாக இருக்கும்போது மட்டுமே தோல்வியடைகிறது, இது அதிகபட்சமாக நிகழ்தகவுடன் நிகழ்கிறது. இந்த கணக்கீட்டின் அடிப்படையில், ஒட்டுமொத்தமாக வழிமுறையால் நிகழ்த்தப்படும் மீறல் சோதனைகளின் எண்ணிக்கை நேரியல் ஆனால் அதிவேகத்தை விட மோசமானது என்பதைக் காட்டலாம். கிளார்க்சன் சீரற்ற மாதிரி நுட்பங்களை அடிப்படையாகக் கொண்ட நேரியல் நிரலாக்கத்திற்கான இரண்டு வழிமுறைகளை வரையறுக்கிறார், ஒரு மறுசுழற்சி வழிமுறை மற்றும் ஒரு மறுசுழற்சி வழிமுறை, மற்றும் மறுசுழற்சி வழிமுறையிலிருந்து மறுசுழற்சி வழிமுறை என்று அழைக்கும் இரண்டின் கலவையை பரிந்துரைக்கிறார். மறுநிகழ்வு வழிமுறை, தோராயமாக உள்ளீட்டு அளவின் வர்க்கமூலம் கொண்ட சீரற்ற மாதிரிகளை மீண்டும் மீண்டும் தேர்ந்தெடுத்து, மாதிரி சிக்கலை மீண்டும் மீண்டும் தீர்க்கிறது, பின்னர் குறைந்தபட்சம் ஒரு அடிப்படை உறுப்பைக் கொண்டிருக்க வேண்டிய மீதமுள்ள கூறுகளின் துணைக்குழுவைக் கண்டுபிடிக்க மீறல் சோதனைகளைப் பயன்படுத்துகிறதுஃ செயல்பாடு மறுநிகழ்வு (S, f) என்பது X: = வெற்று தொகுப்பு மீண்டும் R: = S இன் சீரற்ற துணைக்குழு அளவு d σnB: = R σ க்கு அடிப்படையாக, மீண்டும் மீண்டும் கணக்கிடப்படுகிறது V: = {x | f (B) χ χ f (B ≤ x)} X: = X ≤ V வெற்று திரும்பும் வரை B ஒவ்வொரு மறு செய்கையிலும், எதிர்பார்க்கப்படும் அளவு, மற்றும் காலியாக இல்லாத போதெல்லாம் அதில் குறைந்தது ஒரு பகுதியையாவது உள்ளடக்கும். எனவே, வழிமுறை பெரும்பாலான மறு செய்கைகளில் செயல்படுகிறது, அவை ஒவ்வொன்றும் மீறல் சோதனைகளைச் செய்கின்றன மற்றும் அளவின் துணைப் பிரச்சினைக்கு ஒற்றை தொடர்ச்சியான அழைப்பைச் செய்கின்றன. கிளார்க்சனின் மறு செய்கை வழிமுறை ஒவ்வொரு உறுப்புக்கும் எடைகளை ஒதுக்குகிறது, ஆரம்பத்தில் அவை அனைத்தும் சமமாக இருக்கும். இது சீரற்ற முறையில் இருந்து கூறுகளின் தொகுப்பைத் தேர்ந்தெடுத்து, முந்தைய வழிமுறையைப் போலவே தொகுப்புகளைக் கணக்கிடுகிறது. மொத்த எடை பெரும்பாலான நேரங்களில் மொத்த எடை (நிலையான நிகழ்தகவுடன் நிகழ்கிறது) என்றால், வழிமுறை ஒவ்வொரு உறுப்பின் எடைகளையும் இரட்டிப்பாக்குகிறது, மேலும் இது காலியாக மாறும் வரை இந்த செயல்முறையை மீண்டும் செய்கிறது. ஒவ்வொரு மறு செய்கையிலும், உகந்த அடிப்படையின் எடை மொத்த எடையை விட அதிக விகிதத்தில் அதிகரிப்பதைக் காட்டலாம், இதிலிருந்து வழிமுறை மறு செய்கைகளுக்குள் முடிவடைய வேண்டும். கொடுக்கப்பட்ட சிக்கலைத் தீர்க்க தொடர்ச்சியான வழிமுறையைப் பயன்படுத்துவதன் மூலமும், அதன் தொடர்ச்சியான அழைப்புகளுக்கான தொடர்ச்சியான வழிமுறையை மாற்றுவதன் மூலமும், பின்னர் தொடர்ச்சியான வழிமுறையால் செய்யப்பட்ட அழைப்புகளுக்கான சீடலின் வழிமுறையை மீண்டும் மாற்றுவதன் மூலமும், கொடுக்கப்பட்ட எல்பி-வகை சிக்கலை மீறல் சோதனைகளைப் பயன்படுத்தி தீர்க்க முடியும். ஒரு நேரியல் நிரலுக்கு பயன்படுத்தப்படும்போது, இந்த வழிமுறை ஒரு இரட்டை சிம்ப்ளக்ஸ் முறையாக விளக்கப்படலாம். மீறல் சோதனை மற்றும் அடிப்படை கணக்கீட்டு முதன்மைக்கு அப்பாற்பட்ட சில கூடுதல் கணக்கீட்டு முதன்மைக்குறியீடுகளுடன், இந்த முறையை தீர்மானிக்க முடியும். மற்ற எல். பி-வகை சிக்கல்களால் எப்போதும் நடத்தப்படாத நேரியல் நிரல்களின் கூடுதல் பண்பைப் பயன்படுத்தும் ஒரு வழிமுறையை மடோசெக், ஷாரிர் மற்றும் வெல்ஸ்ல் விவரிக்கிறார்கள், அனைத்து தளங்களும் ஒருவருக்கொருவர் ஒரே கார்டினாலிட்டியைக் கொண்டுள்ளன. ஒரு LP-வகை சிக்கலுக்கு இந்த பண்பு இல்லையென்றால், புதிய போலி கூறுகளைச் சேர்ப்பதன் மூலமும், செயல்பாட்டை மாற்றியமைப்பதன் மூலமும் அதன் பழைய மதிப்பு மற்றும் எண்ணின் வரிசைப்படுத்தப்பட்ட ஜோடியை அகராதியியல் ரீதியாகத் திருப்பித் தருவதன் மூலமும் அதைச் செய்ய முடியும். ஒரு நேரத்தில் எஸ் ஒன்னின் கூறுகளைச் சேர்ப்பதற்குப் பதிலாக, அல்லது கூறுகளின் மாதிரிகளைக் கண்டுபிடிப்பதற்குப் பதிலாக, ஒரு நேரத்தில் உறுப்புகளை அகற்றும் ஒரு வழிமுறையை விவரிக்கவும். ஒவ்வொரு கட்டத்திலும் இது ஒரு அடிப்படையை பராமரிக்கிறது, இது ஆரம்பத்தில் போலி கூறுகளின் தொகுப்பாக இருக்கலாம். இது பின்வரும் போலி குறியீட்டால் விவரிக்கப்படலாம்ஃ செயல்பாடு எம். எஸ். டபிள்யூ (எஸ், எஃப், சி) என்பது எஸ் = சி என்றால், திரும்பும் சி ஒரு சீரற்ற உறுப்பு x ஐத் தேர்வுசெய்கிறது எஸ்\சி. பி = எம். எஸ். டபிள்யூ (எஸ்\எக்ஸ், எஃப், சி) என்றால் எஃப் (பி) ஷ்ணம் எஃப் (பி ஷ்ணம் {எக்ஸ்}) பின்னர் பிஃ = அடிப்படை (பி ஷ்ணம் {எக்ஸ்}) பிஃ = எம். எஸ். டபிள்யூ (எஸ், எஃப், பி) திரும்பும் பி வழிமுறையின் பெரும்பாலான தொடர்ச்சியான அழைப்புகளில், மீறல் சோதனை வெற்றி பெறுகிறது மற்றும் இஃப் ஸ்டேட்மென்ட் தவிர்க்கப்படுகிறது. இருப்பினும், ஒரு சிறிய நிகழ்தகவுடன் மீறல் சோதனை தோல்வியடைகிறது மற்றும் வழிமுறை ஒரு கூடுதல் அடிப்படை கணக்கீடு மற்றும் பின்னர் ஒரு கூடுதல் மறுநிகழ்வு அழைப்பு செய்கிறது. ஆசிரியர்கள் காட்டுவது போல், வழிமுறையின் எதிர்பார்க்கப்படும் நேரம் n இல் நேரியல் மற்றும் இன் வர்க்கமூலத்தில் அதிவேகமானது. இந்த முறையை கிளார்க்சனின் மறுசுழற்சி மற்றும் மறுசுழற்சி நடைமுறைகளுடன் இணைப்பதன் மூலம், இந்த இரண்டு வகையான நேர சார்புகளையும் ஒருவருக்கொருவர் பிரிக்க முடியும், இதன் விளைவாக வெளிப்புற மறுசுழற்சி வழிமுறையில் O (dn) மீறல் சோதனைகளைச் செய்யும் ஒரு வழிமுறை மற்றும் படிமுறையின் கீழ் நிலைகளில் உள்ள வர்க்க மூலத்தில் அதிவேகமான எண். அவுட்லையர்களுடனான மாறுபாடுகள் உகப்பாக்கம் LP-வகை உகப்பாக்கம் சிக்கல்களின் மாறுபாட்டைக் கருதுகிறது, இதில் ஒன்று வழங்கப்படுகிறது, தொகுப்பு மற்றும் புறநிலை செயல்பாடு, ஒரு எண்; மீதமுள்ள தொகுப்பில் புறநிலை செயல்பாட்டை முடிந்தவரை சிறியதாக மாற்றுவதற்காக கூறுகளை அகற்றுவதே பணியாகும். உதாரணமாக, மிகச்சிறிய வட்டம் சிக்கலுக்கு பயன்படுத்தப்படும்போது, இது கொடுக்கப்பட்ட பிளானர் புள்ளிகளின் தொகுப்பைத் தவிர மற்ற அனைத்தையும் கொண்ட மிகச்சிறிய வட்டத்தைக் கொடுக்கும். சீரழியாத அனைத்து எல்பி-வகை சிக்கல்களுக்கும் (அதாவது, அனைத்து தளங்களும் தனித்துவமான மதிப்புகளைக் கொண்ட சிக்கல்கள்) இந்த சிக்கலை சரியான நேரத்தில் தீர்க்க முடியும் என்பதை அவர் காட்டுகிறார், இதன் துணைக்குழுக்களால் வரையறுக்கப்பட்ட எல்பி-வகை சிக்கல்களின் தொகுப்பைத் தீர்ப்பதன் மூலம். சில வடிவியல் உகப்பாக்கம் சிக்கல்கள் LP-வகை சிக்கல்களாக வெளிப்படுத்தப்படலாம், இதில் LP-வகை சூத்திரத்தில் உள்ள கூறுகளின் எண்ணிக்கை உகப்பாக்கம் சிக்கலுக்கான உள்ளீட்டு தரவு மதிப்புகளின் எண்ணிக்கையை விட கணிசமாக அதிகமாக உள்ளது. எடுத்துக்காட்டாக, தளத்தில் உள்ள புள்ளிகளின் தொகுப்பைக் கவனியுங்கள், ஒவ்வொன்றும் நிலையான வேகத்தில் நகர்கின்றன. எந்த நேரத்திலும், இந்த அமைப்பின் விட்டம் அதன் இரண்டு புள்ளிகளுக்கு இடையிலான அதிகபட்ச தூரமாகும். விட்டம் குறைக்கப்படும் நேரத்தைக் கண்டுபிடிப்பதில் உள்ள சிக்கல், குவாசிகன்வெக்ஸ் செயல்பாடுகளின் புள்ளி வாரியாக அதிகபட்சத்தை குறைப்பது, ஒவ்வொரு ஜோடி புள்ளிகளுக்கும் ஒன்று, ஜோடிக்கு இடையிலான யூக்ளிடியன் தூரத்தை நேரத்தின் செயல்பாடாக அளவிடுவது என வடிவமைக்கப்படலாம். எனவே, இது உறுப்புகளின் தொகுப்பில் ஒருங்கிணைந்த பரிமாணம் இரண்டின் எல்பி-வகை சிக்கலாக தீர்க்கப்படலாம், ஆனால் இந்த தொகுப்பு உள்ளீட்டு புள்ளிகளின் எண்ணிக்கையை விட கணிசமாக பெரியது. இது போன்ற மறைமுகமாக வரையறுக்கப்பட்ட எல்பி-வகை சிக்கல்களைத் தீர்ப்பதற்கான ஒரு வழிமுறையை விவரிக்கிறது, இதில் ஒவ்வொரு எல்பி-வகை உறுப்பும் சில மாறிலிகளுக்கு உள்ளீட்டு மதிப்புகளின்-டப்பிள் மூலம் தீர்மானிக்கப்படுகிறது. அவரது அணுகுமுறையைப் பயன்படுத்த, கொடுக்கப்பட்ட எல்பி-வகை அடிப்படை மற்றும் உள்ளீட்டு மதிப்புகளின் தொகுப்புக்கு, எல்பி-வகை சிக்கலுக்கு ஒரு அடிப்படையா என்பதை தீர்மானிக்கக்கூடிய ஒரு முடிவு வழிமுறை இருக்க வேண்டும். சானின் வழிமுறை பின்வரும் படிகளைச் செய்கிறதுஃ உள்ளீட்டு மதிப்புகளின் எண்ணிக்கை சில வரம்பு மதிப்பிற்குக் குறைவாக இருந்தால், அது தீர்மானிக்கும் LP-வகை கூறுகளின் தொகுப்பைக் கண்டுபிடித்து அதன் விளைவாக வெளிப்படையான LP-வகை சிக்கலைத் தீர்க்கவும். இல்லையெனில், உள்ளீட்டு மதிப்புகளை சம அளவிலான துணைக்குழுக்களை விட பொருத்தமான எண்ணாக பிரிக்கவும். மறைமுகமாக வரையறுக்கப்பட்ட LP-வகை சிக்கலைத் தீர்ப்பதற்கான புறநிலை செயல்பாடு என்றால், துணைக்குழுக்களின் தொகுப்புகளை சேகரிப்பின் ஒன்றியத்தின் மதிப்பிற்கு வரைபடமாக்கும் ஒரு செயல்பாட்டை வரையறுக்கவும். பின்னர் துணைக்குழுக்களின் தொகுப்பு மற்றும் புறநிலை செயல்பாடு ஒரு LP-வகை சிக்கலை வரையறுக்கிறது, இது தீர்க்கப்பட வேண்டிய மறைமுகமான சிக்கலின் அதே பரிமாணமாகும். கிளார்க்சனின் வழிமுறையைப் பயன்படுத்தி வரையறுக்கப்பட்ட (வெளிப்படையான) LP-வகை சிக்கலைத் தீர்க்கவும், இது ஒரு நேரியல் எண்ணிக்கையிலான மீறல் சோதனைகள் மற்றும் அடிப்படைக் மதிப்பீடுகளின் பல்லுறுப்புக்கோவை எண்ணிக்கையைச் செய்கிறது. சானின் வழிமுறைக்கு தொடர்ச்சியான அழைப்புகள் மூலம் அடிப்படை மதிப்பீடுகள் செய்யப்படலாம், மேலும் விதிமீறல் சோதனைகள் முடிவு வழிமுறைக்கு அழைப்புகள் மூலம் செய்யப்படலாம். முடிவு வழிமுறை குறைந்தபட்சம் உள்ளீட்டு அளவின் செயல்பாடாக பல்லுறுப்புக்கோவையாக வளரும் நேரத்தை எடுக்கும் என்ற அனுமானத்துடன், ஒரு வெளிப்படையான LP சூத்திரத்திற்கு மாறுவதற்கான நுழைவாயில் மற்றும் பகிர்வில் உள்ள துணைக்குழுக்களின் எண்ணிக்கையை தேர்வு செய்யலாம் என்பதை சான் காட்டுகிறார். உதாரணமாக, நகரும் புள்ளிகளின் குறைந்தபட்ச விட்டத்திற்கு, முடிவு வழிமுறை ஒரு குறிப்பிட்ட நேரத்தில் புள்ளிகளின் தொகுப்பின் விட்டத்தை மட்டுமே கணக்கிட வேண்டும், இது சுழலும் காலிபர்கள் நுட்பத்தைப் பயன்படுத்தி சரியான நேரத்தில் தீர்க்கக்கூடிய ஒரு சிக்கலாகும். எனவே, விட்டம் குறைக்கப்படும் நேரத்தைக் கண்டுபிடிப்பதற்கான சானின் வழிமுறையும் நேரம் எடுக்கும். காலப்போக்கில்-பரிமாண யூக்ளிடியன் இடத்தில் கொடுக்கப்பட்ட புள்ளிகளின் தொகுப்பின் மத்தியில் அதிகபட்ச டுகி ஆழத்தின் புள்ளியைக் கண்டறிய சான் இந்த முறையைப் பயன்படுத்துகிறார். ஒரு குவிந்த பலகோணத்தில் சீரான விநியோகத்திற்கான அதிகபட்ச டுகி ஆழத்தின் புள்ளியைக் கண்டறிய இதேபோன்ற நுட்பம் பயன்படுத்தப்பட்டது. வரலாறு மற்றும் தொடர்புடைய சிக்கல்கள் நேரியல் நிரலாக்கத்திற்கான நேரியல் நேர வழிமுறைகளின் கண்டுபிடிப்பு மற்றும் அதே வழிமுறைகள் பல சந்தர்ப்பங்களில் நேரியல் நிரல்களாக இல்லாத வடிவியல் உகப்பாக்கம் சிக்கல்களைத் தீர்க்க பயன்படுத்தப்படலாம் என்ற அவதானிப்பு குறைந்தது மூன்று மாறிகள் கொண்ட நேரியல் நிரல்கள் மற்றும் மிகச்சிறிய வட்ட சிக்கல் ஆகிய இரண்டிற்கும் ஒரு நேரியல் எதிர்பார்க்கப்பட்ட நேர வழிமுறையை வழங்கியவர். இருப்பினும், மெகிடோ நேரியல் நிரலாக்கத்தின் பொதுமைப்படுத்தலை இணைப்பதை விட வடிவியல் ரீதியாக வடிவமைத்தார், இது தொகுப்புகளின் அமைப்புகளில் ஒரு சுருக்கமான சிக்கலாக இல்லாமல் ஒரு குவிந்த உகப்பாக்கம் சிக்கலாகும். இதேபோல், மற்றும் கிளார்க்சன் (1988 மாநாட்டு பதிப்பில்) அவற்றின் முறைகள் குவிந்த நிரல்களுக்கும் நேரியல் நிரல்களுக்கும் பயன்படுத்தப்படலாம் என்பதைக் கவனித்தார். குறைந்தபட்ச அடைக்கப்பட்ட நீள்வட்ட சிக்கலை ஒரு சிறிய எண்ணிக்கையிலான நேரியல் அல்லாத கட்டுப்பாடுகளைச் சேர்ப்பதன் மூலம் குவிந்த உகப்பாக்கம் சிக்கலாக வடிவமைக்க முடியும் என்பதைக் காட்டியது. குறைந்த பரிமாண நேரியல் நிரலாக்கம் மற்றும் தொடர்புடைய சிக்கல்களுக்கான கால வரம்புகளை மேம்படுத்த சீரற்றமயமாக்கலின் பயன்பாடு கிளார்க்சன் மற்றும் ஆல் முன்னோடியாக இருந்தது. வட்டாரம் மற்றும் மோனோடோனிசிட்டி ஆகியவற்றின் கோட்பாடுகளை திருப்திப்படுத்தும் செயல்பாடுகளின் அடிப்படையில் LP-வகை சிக்கல்களின் வரையறை இதிலிருந்து வருகிறது, ஆனால் அதே காலக்கட்டத்தில் மற்ற எழுத்தாளர்கள் நேரியல் நிரல்களின் மாற்று ஒருங்கிணைந்த பொதுமைப்படுத்தல்களை உருவாக்கினர். உதாரணமாக, உருவாக்கிய கட்டமைப்பில், செயல்பாடு அதன் துணைக்குழுக்களில் மொத்த வரிசையால் மாற்றப்படுகிறது. மொத்த வரிசையை உருவாக்க ஒரு எல்பி-வகை சிக்கலில் உறவுகளை உடைக்க முடியும், ஆனால் ஒருங்கிணைந்த பரிமாணத்தின் அதிகரிப்பின் இழப்பில் மட்டுமே. கூடுதலாக, LP-வகை சிக்கல்களைப் போலவே, கார்ட்னர் கூறுகளின் துணைக்குழுக்களில் கணக்கீடுகளைச் செய்வதற்கான சில முதன்மையானவற்றை வரையறுக்கிறார்; இருப்பினும், அவரது முறைப்படுத்தல் ஒருங்கிணைந்த பரிமாணத்தின் ஒப்புமையைக் கொண்டிருக்கவில்லை. நேரியல் நிரல்கள் மற்றும் நேரியல் நிரப்பு சிக்கல்கள் ஆகிய இரண்டின் மற்றொரு சுருக்கமான பொதுமைப்படுத்தல், பல எழுத்தாளர்களால் வடிவமைக்கப்பட்டு பின்னர் ஆய்வு செய்யப்பட்டது, ஹைபர்கியூபின் விளிம்புகளின் நோக்குநிலைகளைப் பற்றியது, ஹைபர்கியூபின் ஒவ்வொரு முகமும் (முகமாக முழு ஹைபர்கியூப் உட்பட) ஒரு தனித்துவமான மூழ்கி, வெளிச்செல்லும் விளிம்புகள் இல்லாத ஒரு உச்சி. இந்த வகை நோக்குநிலை ஒரு எல்பி-வகை சிக்கலில் இருந்து ஒரு ஹைபர்கியூபின் செங்குத்துகளுடன் எஸ் இன் துணைக்குழுக்களை ஒத்திருப்பதன் மூலம் உருவாக்கப்படலாம், இதனால் இரண்டு துணைக்குழுக்கள் ஒரே உறுப்பால் வேறுபடுகின்றன, தொடர்புடைய செங்குத்துகள் அருகில் இருந்தால் மட்டுமே, மற்றும் அண்டை செட்களுக்கு இடையிலான விளிம்பை வேறு திசையில் நோக்குவதன் மூலம். இதன் விளைவாக வரும் நோக்குநிலை ஒரு கூடுதல் பண்பைக் கொண்டுள்ளது, இது ஒரு இயக்கப்படும் அசைக்ளிக் வரைபடத்தை உருவாக்குகிறது, இதிலிருந்து ஒரு சீரற்ற வழிமுறை முழு ஹைபர்கியூபின் (எல்பி-வகை சிக்கலின் உகந்த அடிப்படை) தனித்துவமான மூழ்கியைக் கண்டுபிடிக்க முடியும் என்பதைக் காட்டலாம். மீறல் இடங்களின் மிக சமீபத்தில் உருவாக்கப்பட்ட கட்டமைப்பு LP-வகை சிக்கல்களை பொதுமைப்படுத்துகிறது, அதாவது ஒவ்வொரு LP-வகை சிக்கலையும் மீறல் இடத்தால் மாதிரியாக்கலாம், ஆனால் அதற்கு நேர்மாறாக இருக்க வேண்டிய அவசியமில்லை. மீறல் இடைவெளிகள் எல்பி-வகை சிக்கல்களைப் போலவே வரையறுக்கப்படுகின்றன, ஒரு செயல்பாட்டின் மூலம் புறநிலை செயல்பாட்டு மதிப்புகளுக்கு அமைப்புகளை வரைபடமாக்குகிறது, ஆனால் மதிப்புகள் வரிசைப்படுத்தப்படவில்லை. வரிசைப்படுத்தல் இல்லாத போதிலும், ஒவ்வொரு தொகுப்பிலும் நன்கு வரையறுக்கப்பட்ட தளங்கள் உள்ளன (முழு தொகுப்பின் அதே மதிப்புடன் கூடிய குறைந்தபட்ச தொகுப்புகள்) அவை எல்பி-வகை சிக்கல்களுக்கான கிளார்க்சனின் வழிமுறைகளின் மாறுபாடுகளால் காணப்படுகின்றன. உண்மையில், கிளார்க்சனின் வழிமுறைகளால் தீர்க்கக்கூடிய அமைப்புகளை மீறுபவர் இடைவெளிகள் சரியாக வகைப்படுத்துவதாகக் காட்டப்பட்டுள்ளது. குறிப்புகள் குறிப்புகள். . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . கணக்கீட்டு வடிவியல் நேரியல் நிரலாக்கம்