Graver basis
பயன்பாட்டு கணிதத்தில், கிரேவர் தளங்கள் பல்லுறுப்புக்கோவை நேரத்தில் நேரியல் மற்றும் பல்வேறு நேரியல் அல்லாத முழு எண் நிரலாக்க சிக்கல்களின் மறுசீரமைப்பு தீர்வுகளை செயல்படுத்துகின்றன. அவை ஜாக் ஈ. கிரேவரால் அறிமுகப்படுத்தப்பட்டன. கிராப்னர் தளங்களின் கோட்பாட்டுடன் அவற்றின் தொடர்பு பெர்ண்ட் ஸ்டர்ம்ஃபெல்ஸால் விவாதிக்கப்பட்டது. கிரேவர் தளங்களின் வழிமுறைக் கோட்பாடு மற்றும் முழு எண் நிரலாக்கத்திற்கான அதன் பயன்பாடு ஆகியவை ஷ்முயெல் ஓன்னால் விவரிக்கப்பட்டுள்ளன. முறையான வரையறை ஒரு m × n முழு எண் மேட்ரிக்ஸின் கிரேவர் அடிப்படை என்பது அனைத்து i க்கும் எப்போது மற்றும் அனைத்திற்கும் வரையறுக்கப்பட்ட ஒரு பகுதி வரிசையின் கீழ் தொகுப்பில் உள்ள குறைந்தபட்ச உறுப்புகளின் வரையறுக்கப்பட்ட தொகுப்பாகும். எடுத்துக்காட்டாக, கிரேவர் அடிப்படையானது திசையன்கள் (2,-1,0), (0,-1,2), (1,0,-1), (1,-1,1) மற்றும் அவற்றின் எதிர்மறைகளைக் கொண்டுள்ளது. கிரேவர் தளங்களைப் பயன்படுத்தி முழு எண் நிரலாக்கத்தை தீர்ப்பது என்பது நேரியல் ஏற்றத்தாழ்வுகளின் அமைப்பை திருப்திப்படுத்தும் முழு எண் புள்ளிகளின் தொகுப்பின் மீது ஒரு நேரியல் அல்லது நேரியல் அல்லாத புறநிலை செயல்பாட்டை மேம்படுத்துவதில் உள்ள சிக்கலாகும். முறைப்படி, இதை நிலையான வடிவத்தில் பின்வருமாறு எழுதலாம்ஃ இது மிகவும் அடிப்படை தனித்துவமான உகப்பாக்கம் சிக்கல்களில் ஒன்றாகும் மற்றும் மிகவும் பரந்த மாடலிங் சக்தி மற்றும் பல்வேறு பகுதிகளில் ஏராளமான பயன்பாடுகளைக் கொண்டுள்ளது, ஆனால் பொதுவாக கீழே குறிப்பிட்டுள்ளபடி கணக்கீட்டில் மிகவும் கடினமாக உள்ளது. இருப்பினும், கிரேவர் அடிப்படையைப் பொறுத்தவரை, நேரியல் மற்றும் பல்வேறு நேரியல் அல்லாத புறநிலை செயல்பாடுகளின் சிக்கலை அடுத்ததாக விளக்கியது போல் பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்க முடியும். நேரியல் முழு எண் நிரலாக்கம் மிகவும் நன்கு ஆராயப்பட்ட வழக்கு, நேரியல் முழு எண் நிரலாக்கமாகும், அனைத்து மாறிகளும் கீழே மற்றும் மேலே இருந்து வரம்புக்குட்பட்டவை என்று கருதலாம்ஃ அத்தகைய வரம்புகள் கையில் உள்ள பயன்பாட்டில் இயற்கையாகவே தோன்றும், அல்லது எந்த உகந்த தீர்வுகளையும் இழக்காமல் செயல்படுத்தப்படலாம். ஆனால், நேரியல் புறநிலை செயல்பாடுகளுடன் கூட சிக்கல் NP-கடினமானது, எனவே பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்க முடியாது. இருப்பினும், கிரேவர் அடிப்படை பின்வரும் பண்புகளைக் கொண்டுள்ளது. சாத்தியமான ஒவ்வொரு புள்ளிக்கும் x: ஒன்று x உகந்ததாகும் (அதாவது, கட்டுப்பாடுகளைக் குறைக்கிறது); அல்லது ஒரு திசையன் g உள்ளது, அதாவது x + g சாத்தியமானது மற்றும் (அதாவது, x ஐ கிரேவர் அடிப்படையின் ஒரு உறுப்பைச் சேர்ப்பதன் மூலம் மேம்படுத்தலாம்). எனவே, கிரேவர் அடிப்படையைப் பொறுத்தவரை, ஐஎல்பி பின்வரும் எளிய மறு செய்கை வழிமுறையைப் பயன்படுத்தி பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்கப்படலாம். சில ஆரம்ப சாத்தியமான புள்ளி x கொடுக்கப்பட்டுள்ளது என்று முதலில் வைத்துக்கொள்வோம். முடிந்தால், பின்வரும் மறு செய்கையை மீண்டும் செய்யுங்கள்ஃ x + qg வரம்புகளை மீறாத வகையில் நேர்மறை முழு எண் q மற்றும் உறுப்பு g ஐக் கண்டறியவும் மற்றும் சிறந்த முன்னேற்றத்தை அளிக்கவும்; x: = x + qg ஐ புதுப்பித்து அடுத்த மறு செய்கைக்குச் செல்லுங்கள். கடைசி புள்ளி x உகந்ததாகும் மற்றும் மறு செய்கைகளின் எண்ணிக்கை பல்லுறுப்புக்கோவை ஆகும். ஒரு ஆரம்ப சாத்தியமான புள்ளியைக் கண்டறிய, பொருத்தமான துணைத் திட்டத்தை அமைத்து இதே பாணியில் தீர்க்க முடியும். நேரியல் அல்லாத முழு எண் நிரலாக்கம் பொதுவான புறநிலை செயல்பாடுகளைப் பொறுத்தவரை f, மாறிகள் வரம்பற்றதாக இருந்தால், சிக்கல் உண்மையில் கணக்கிட முடியாததாக இருக்கலாம்ஃ இது ஹில்பர்ட்டின் 10 வது சிக்கலின் தீர்விலிருந்து பின்வருமாறு (பார்க்க), எந்த வழிமுறையும் இல்லை, இது 58 மாறிகளில் டிகிரி 8 இன் முழு எண் பல்லுறுப்புக்கோவை f ஐக் கொடுத்தால், அனைத்து 58 பரிமாண முழு எண் திசையன்களுக்கும் f இன் குறைந்தபட்ச மதிப்பு 0 ஆக இருக்கிறதா என்பதை தீர்மானிக்கிறது. இருப்பினும், மாறிகள் வரம்புக்குட்பட்டதாக இருக்கும்போது, பல நேரியல் அல்லாத புறநிலை செயல்பாடுகளுக்கு பல்லுறுப்புக்கோவை நேரத்தில் கிரேவர் அடிப்படையைப் பயன்படுத்தி சிக்கலைத் தீர்க்க முடியும், இதில் பின்வருவன அடங்கும்ஃ வடிவத்தின் பிரிக்கக்கூடிய-குவியல் செயல்பாடுகள்; குறிப்பாக ஒவ்வொரு நேர்மறை முழு எண் p க்கும் p-நெறிமுறை; கலப்பு-கான்காவ் செயல்பாடுகள் f (x) = g (Wx), W என்பது d நிலையான ஒரு d × n முழு எண் மேட்ரிக்ஸ், மற்றும் g என்பது ஒரு d-மாறுபட்ட குழிவான செயல்பாடு; சில (in)-வரையறுக்கப்பட்ட இருபடி மற்றும் உயர் டிகிரி பல்லுறுப்புக்கோவை செயல்பாடுகள். சில பயன்பாடுகள் பல பரிமாண அட்டவணைகள் மூன்று பரிமாண அட்டவணைகளில் பின்வரும் உகப்பாக்கம் சிக்கலைக் கருத்தில் கொள்ளுங்கள், பரிந்துரைக்கப்பட்ட வரி தொகைகளுடன், எதிர்மறை அல்லாத முழு எண்களுடன் (அதன் அதிகபட்ச மதிப்பு மேலே உள்ள அனைத்து மாறிகளையும் மறைமுகமாக கட்டுப்படுத்துகிறது). இந்த அமைப்பின் வரையறுக்கும் மேட்ரிக்ஸ் (lm + ln + mn) × (lmn) மூலம் குறிக்கவும். இந்த மேட்ரிக்ஸ் பொதுவாக முற்றிலும் ஒரே மாதிரியாக இல்லை என்பதை நினைவில் கொள்க. இருப்பினும், ஒவ்வொரு நிலையான l மற்றும் m க்கும், அதன் கிரேவர் அடிப்படையை n இல் பல்லுறுப்புக்கோவை இருக்கும் நேரத்தில் கணக்கிட முடியும் என்று காட்டப்பட்டது. மேலே குறிப்பிடப்பட்ட முடிவுகள் இந்த சிக்கலை நிலையான l மற்றும் m மற்றும் மாறி n க்கான பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்க அனுமதிக்கின்றன. அட்டவணையின் ஒரு பக்கம் l மட்டுமே நிலையாக இருந்தால் (l = 3 உடன் கூட) m மற்றும் n இரண்டும் மாறுபடும் போது, சிக்கல் NP கடினமானது, காட்டப்பட்டுள்ளபடி. மேலும் பொதுவாக, உயர் பரிமாண அட்டவணை சிக்கல்களுக்கு ஒத்த நேர்மறையான முடிவுகள் உள்ளன (அறிமுகப்படுத்தப்பட்டது): ஒவ்வொரு நிலையான d க்கும், (அல்லாத)-மாறி n மற்றும் பரிந்துரைக்கப்பட்ட விளிம்புகளைக் கொண்ட அட்டவணைகளின் மீது நேரியல் உகப்பாக்கம் பல்லுறுப்புக்கோவை நேரத்தில் செய்யப்படலாம். இது புள்ளிவிவர தரவுத்தளங்களில் பாதுகாப்பு சிக்கல்கள் மற்றும் தனியுரிமையை உள்ளிடுவதற்கான கூடுதல் பயன்பாடுகளைக் கொண்டுள்ளது. பல-பொருட்கள் ஓட்டங்கள் k வகையான முழு எண் பொருட்களை m சப்ளையர்களிடமிருந்து n நுகர்வோருக்கு வழங்குதல், நுகர்வு மற்றும் திறன் கட்டுப்பாடுகளுக்கு உட்பட்டு வழிநடத்தும் முழு எண் பல-பொருட்கள் ஓட்ட சிக்கலைக் கவனியுங்கள், இதனால் வளைவுகளில் நேரியல் அல்லது நெரிசல் சார்ந்த குவிந்த செலவுகளின் கூட்டுத்தொகையைக் குறைக்கலாம். பின்னர் ஒவ்வொரு நிலையான k மற்றும் m க்கும், வரையறுக்கும் அமைப்பின் கிரேவர் அடிப்படையை கணக்கிடலாம் மற்றும் இதன் விளைவாக பிரிக்கக்கூடிய-கன்வெக்ஸ் புறநிலை செயல்பாட்டை நேரத்தில் குறைக்கலாம், இது நுகர்வோரின் மாறி எண் n இல் பல்லுறுப்புக்கோவை மற்றும் மீதமுள்ள தரவுகளில் உள்ளது. பிற பயன்பாடுகள் கிரேவர் தளங்களின் வழிமுறைக் கோட்பாட்டின் பல பயன்பாடுகளும் அடங்கும்ஃ சீரற்ற முழு எண் நிரலாக்கம், என்-மடிப்பு முழு எண் நிரலாக்கம், என்-மடிப்பு 4-தொகுதி சிதைக்கக்கூடிய முழு எண் நிரலாக்கம், கிளஸ்டரிங், புள்ளிவிவர தரவுத்தளங்களில் வெளிப்படுத்தல் கட்டுப்பாடு மற்றும் பிரிக்க முடியாத பொருட்களின் நியாயமான ஒதுக்கீடு. இந்த பயன்பாடுகளில் சிலவற்றில் தொடர்புடைய கிரேவர் அடிப்படையை பல்லுறுப்புக்கோவை நேரத்தில் கணக்கிட முடியாது, ஆனால் பல்லுறுப்புக்கோவை நேரத்தில் பயன்படுத்த அனுமதிக்கும் மறைமுக வழியில் அணுகலாம். ஒவ்வொரு (எல்லைக்குட்பட்ட) முழு எண் நிரலாக்க சிக்கலும் சில m மற்றும் n மற்றும் சில வரி தொகைகளுக்கு மேலே விவாதிக்கப்பட்ட 3 × m × n அட்டவணை சிக்கலுக்கு துல்லியமாக சமம் என்று காட்டப்பட்டது. எனவே, அத்தகைய 3 × m × n அட்டவணை சிக்கல்கள் முழு எண் நிரலாக்கத்திற்கு உலகளாவியவை. மேலும், ஒவ்வொரு நிலையான m க்கும், முழு எண் நிரல்களின் விளைவாக வரும் வகுப்பை மேலே விவரிக்கப்பட்ட மறு செய்கை கிரேவர் அடிப்படை முறை மூலம் பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்க முடியும். எனவே அட்டவணை அகலம் m அனைத்து முழு எண் நிரலாக்க சிக்கல்களின் அளவுருவை வழங்குகிறது. முழு எண் நிரலாக்கத்திற்கான தோராயங்களின் படிநிலை மேலே விவாதிக்கப்பட்ட உலகளாவிய 3 × m × n அட்டவணை சிக்கலை வரையறுக்கும் மேட்ரிக்ஸின் கிரேவர் அடிப்படையால் குறிக்கப்படுகிறது. இதன் உறுப்புகள் 3 × m × n அட்டவணைகள் மற்றும் அனைத்து வரி தொகைகளும் 0 க்கு சமமாக இருக்கும். அத்தகைய அட்டவணையின் வகை அதன் பூஜ்ஜியமற்ற 3 × மீ அடுக்குகளின் எண்ணிக்கை ஆகும். ஒரு வரையறுக்கப்பட்ட கிரேவர் சிக்கலான செயல்பாடு g (m) உள்ளது என்று மாறிவிடும், அதாவது எந்த n க்கும், கிரேவர் அடிப்படையின் எந்த உறுப்பின் வகையும் அதிகபட்சமாக g (m) ஆகும். கிரேவர் அடிப்படை என்பது கிரேவர் அடிப்படையின் பொருத்தமான உட்பொதிக்கப்பட்ட நகல்களின் ஒன்றிணைப்பாகும். நடைமுறையில் ஒரு தன்னிச்சையான முழு எண் நிரலாக்க சிக்கலை தோராயமாக தீர்க்க, பின்வருமாறு தொடரவும். மேலே குறிப்பிட்டுள்ள உலகளாவிய தன்மையால் இயக்கப்பட்ட பொருத்தமான 3 × m × n அட்டவணை சிக்கலில் முதலில் அதை உட்பொதிக்கவும். இப்போது தோராயங்களின் பின்வரும் படிநிலையைப் பயன்படுத்துங்கள். இந்த படிநிலையின் நிலை k இல், அதிகபட்சம் k இல் அந்த வகை கூறுகளை மட்டுமே உள்ளடக்கிய துணைக்குழுவாக இருக்கட்டும்; 3 × m × n அட்டவணை சிக்கலில் உட்பொதிக்கப்பட்ட முழு எண் நிரலாக்க சிக்கலுக்கு முடிந்தவரை சிறந்த சாத்தியமான புள்ளியைப் பெற முடிந்தவரை மறு செய்கை வழிமுறையில் இந்த தோராயத்தைப் பயன்படுத்தவும்; இந்த புள்ளியின் புறநிலை செயல்பாட்டு மதிப்பு திருப்திகரமாக இருந்தால் (நேரியல் நிரலாக்க தளர்வுகளின் மதிப்புடன் ஒப்பிடுகையில்), பின்னர் இந்த புள்ளியைப் பயன்படுத்தவும்; இல்லையெனில் k ஐ அதிகரித்து படிநிலையின் அடுத்த நிலைக்குச் செல்லுங்கள். எந்தவொரு நிலையான நிலை k க்கும், கிரேவர் அடிப்படையின் தோராயமானது பல்லுறுப்புக்கோவை கார்டினாலிட்டியைக் கொண்டுள்ளது மற்றும் அந்த நேரத்தில் கணக்கிடப்படலாம் என்பதைக் காட்டலாம். நிலையான அளவுரு டிராக்டபிலிட்டிஃ பல்லுறுப்புக்கோவை முதல் கன நேர சிக்கலானது மேலே விவாதிக்கப்பட்ட சில பயன்பாடுகளைத் தீர்ப்பதற்கான நேர சிக்கலானது, அதாவது பல பரிமாண அட்டவணை சிக்கல்கள், பன்முகத்தன்மை ஓட்டம் சிக்கல்கள் மற்றும் என்-மடங்கு நிரலாக்க சிக்கல்கள், தொடர்புடைய கிரேவர் அடிப்படையின் கார்டினாலிட்டியால் ஆதிக்கம் செலுத்துகிறது, இது பொதுவாக பெரிய டிகிரி ஜி கொண்ட ஒரு பல்லுறுப்புக்கோவை ஆகும், இது அமைப்பின் பொருத்தமான கிரேவர் சிக்கலானது. மிகவும் வேகமான வழிமுறை வழங்கப்படுகிறது, இது ஒவ்வொரு மறு செய்கையிலும் x + qg ஐ q நேர்மறை முழு எண் மற்றும் g உறுப்புடன் கிரேவர் அடிப்படையை வெளிப்படையாக உருவாக்காமல், கனசதுர நேரத்தில் அமைப்பைப் பொருட்படுத்தாமல் சிறந்த முன்னேற்றத்தைக் கண்டறிகிறது. அளவுருப்படுத்தப்பட்ட சிக்கலின் சொற்களில், இந்த சிக்கல்கள் அனைத்தும் பொருத்தமான அளவுருவாகவும், குறிப்பாக l × m × n அட்டவணை சிக்கல்கள் l மற்றும் m ஆல் அளவுருவாகவும், நிலையான அளவுரு கையாளக்கூடியவை என்பதை இது குறிக்கிறது. கார்டனின் லெம்மாவையும் பார்க்கவும்-பூஜ்ஜிய முழு எண் மேட்ரிக்ஸ்கள் தொடர்பான மற்றொரு கருவி. குறிப்புகள் நேரியல் நிரலாக்கம்