Klee's measure problem
கணக்கீட்டு வடிவவியலில், க்ளீயின் அளவீட்டு சிக்கல் என்பது (பன்முக) செவ்வக வரம்புகளின் ஒன்றிணைப்பின் அளவீட்டை எவ்வளவு திறமையாக கணக்கிட முடியும் என்பதை தீர்மானிக்கும் சிக்கலாகும். இங்கே, ஒரு டி-பரிமாண செவ்வக வரம்பு உண்மையான எண்களின் டி இடைவெளிகளின் கார்ட்டீசியன் பெருக்கல் என்று வரையறுக்கப்படுகிறது, இது Rd இன் துணைக்குழுவாகும். இடைவெளிகளின் சங்கமத்தின் நீளத்தை கணக்கிடுவதற்கான ஒரு வழிமுறையை வழங்கிய விக்டர் க்ளீயின் பெயரால் இந்த சிக்கல் பெயரிடப்பட்டுள்ளது (வழக்கு d = 1) இது பின்னர் கணக்கீட்டு சிக்கலான கோட்பாட்டின் அர்த்தத்தில் உகந்த திறனுடன் இருப்பதாகக் காட்டப்பட்டது. இரு பரிமாண செவ்வக வரம்புகளின் ஒன்றியத்தின் பரப்பளவைக் கணக்கிடுவதற்கான கணக்கீட்டு சிக்கலும் இப்போது அறியப்படுகிறது, ஆனால் வழக்கு d ≤ 3 ஒரு திறந்த சிக்கலாகவே உள்ளது. வரலாறு மற்றும் வழிமுறைகள் 1977 ஆம் ஆண்டில், விக்டர் க்ளீ பின்வரும் சிக்கலைக் கருத்தில் கொண்டார்ஃ உண்மையான கோட்டில் n இடைவெளிகளின் தொகுப்பைக் கொடுத்தால், அவற்றின் ஒன்றியத்தின் நீளத்தைக் கணக்கிடுங்கள். பின்னர் அவர் கணக்கீட்டு சிக்கலுடன் (அல்லது "இயங்கும் நேரம்") இந்த சிக்கலைத் தீர்ப்பதற்கான ஒரு வழிமுறையை முன்வைத்தார்-இந்த அறிக்கையின் அர்த்தத்திற்கு பிக் ஓ குறியீட்டைப் பார்க்கவும். இடைவெளிகளை வரிசைப்படுத்துவதை அடிப்படையாகக் கொண்ட இந்த வழிமுறை, பின்னர் மைக்கேல் ஃப்ரெட்மேன் மற்றும் புரூஸ் வெய்ட் (1978) ஆகியோரால் உகந்ததாக காட்டப்பட்டது. பின்னர் 1977 ஆம் ஆண்டில், ஜான் பென்ட்லி இந்த சிக்கலின் இரு பரிமாண ஒப்புமையைக் கருத்தில் கொண்டார்ஃ n செவ்வகங்களின் தொகுப்பைக் கொடுத்தால், அவற்றின் சங்கமத்தின் பரப்பளவைக் கண்டறியவும். அவர் ஒரு சிக்கலான வழிமுறையையும் பெற்றார், இப்போது பென்ட்லியின் வழிமுறை என்று அழைக்கப்படுகிறது, இது சிக்கலை n 1 பரிமாண சிக்கல்களுக்கு குறைப்பதை அடிப்படையாகக் கொண்டதுஃ இது பகுதி முழுவதும் ஒரு செங்குத்து கோட்டை துடைப்பதன் மூலம் செய்யப்படுகிறது. இந்த முறையைப் பயன்படுத்தி, தொழிற்சங்கத்தின் பரப்பளவை வெளிப்படையாக தொழிற்சங்கத்தை உருவாக்காமல் கணக்கிட முடியும். பென்ட்லியின் வழிமுறை இப்போது உகந்ததாக அறியப்படுகிறது (இரு பரிமாண விஷயத்தில்), மேலும் இது கணினி கிராபிக்ஸ் மற்றும் பிற பகுதிகளில் பயன்படுத்தப்படுகிறது. இந்த இரண்டு சிக்கல்களும் மிகவும் பொதுவான கேள்வியின் 1-மற்றும் 2-பரிமாண நிகழ்வுகளாகும்ஃ nd-பரிமாண செவ்வக வரம்புகளின் தொகுப்பைக் கொடுத்தால், அவற்றின் இணைப்பின் அளவைக் கணக்கிடுங்கள். இந்த பொதுவான சிக்கல் க்ளீயின் அளவீட்டு சிக்கலாகும். டி-பரிமாண வழக்குக்கு பொதுமைப்படுத்தப்படும்போது, பென்ட்லியின் வழிமுறை ஒரு இயங்கும் நேரத்தைக் கொண்டுள்ளது. இது உகந்ததாக இல்லை, ஏனென்றால் இது டி-பரிமாண சிக்கலை என் (டி-1) பரிமாண சிக்கல்களாக மட்டுமே சிதைக்கிறது, மேலும் அந்த துணை சிக்கல்களை மேலும் சிதைக்காது. 1981 ஆம் ஆண்டில், ஜான் வான் லீயுவென் மற்றும் டெரெக் வூட் ஆகியோர் டைனமிக் குவாட்ரீஸைப் பயன்படுத்தி இந்த வழிமுறையின் இயங்கும் நேரத்தை d ≤ 3 ஆக மேம்படுத்தினர். 1988 ஆம் ஆண்டில், மார்க் ஓவர்மார்ஸ் மற்றும் சீ யாப் ஆகியோர் d ≤ 3 க்கான ஒரு வழிமுறையை முன்மொழிந்தனர். அவர்களின் வழிமுறை ஒரு கேடி-மரத்தைப் போன்ற ஒரு குறிப்பிட்ட தரவு கட்டமைப்பைப் பயன்படுத்தி சிக்கலை இரு பரிமாண கூறுகளாக சிதைத்து, அந்த கூறுகளை திறம்பட ஒருங்கிணைக்கிறது; இரு பரிமாண சிக்கல்கள் ஒரு ட்ரெல்லிஸ் கட்டமைப்பைப் பயன்படுத்தி திறம்பட தீர்க்கப்படுகின்றன. பென்ட்லியின் வழிமுறையை விட அறிகுறியற்ற முறையில் வேகமாக இருந்தாலும், அதன் தரவு கட்டமைப்புகள் கணிசமாக அதிக இடத்தைப் பயன்படுத்துகின்றன, எனவே இது n அல்லது d பெரியதாக இருக்கும் சிக்கல்களில் மட்டுமே பயன்படுத்தப்படுகிறது. 1998 ஆம் ஆண்டில், D என்பது 3 அல்லது 4 ஆக இருக்கும் பொதுவான சிறப்பு நிகழ்வுகளுக்கு அதே அறிகுறியற்ற இயங்கும் நேரத்துடன் ஒரு எளிய வழிமுறையை போக்டன் கிளெபஸ் முன்மொழிந்தார். 2013 ஆம் ஆண்டில், திமோதி எம். சான் ஒரு எளிய வழிமுறையை உருவாக்கினார், இது மாறும் தரவு கட்டமைப்புகளின் தேவையைத் தவிர்க்கிறது மற்றும் மடக்கைக் காரணியை நீக்குகிறது, இது d ≤3 க்கு நன்கு அறியப்பட்ட இயங்கும் நேரத்தைக் குறைக்கிறது. அறியப்பட்ட வரம்புகள் எந்தவொரு d க்கும் அறியப்பட்ட ஒரே கீழ் வரம்பு, மற்றும் இந்த இயங்கும் நேரத்துடன் உகந்த வழிமுறைகள் d = 1 மற்றும் d = 2 க்கு அறியப்படுகின்றன. சான் வழிமுறை d ≤ 3 க்கு ஒரு மேல் வரம்பை வழங்குகிறது, எனவே d ≤ 3 க்கு, வேகமான வழிமுறைகள் சாத்தியமா அல்லது மாற்றாக இறுக்கமான கீழ் வரம்புகளை நிரூபிக்க முடியுமா என்பது ஒரு திறந்த கேள்வியாக உள்ளது. குறிப்பாக, வழிமுறையின் இயக்க நேரம் d ஐப் பொறுத்ததா என்பது திறந்திருக்கும். கூடுதலாக, சிறப்பு நிகழ்வுகளைக் கையாளக்கூடிய வேகமான வழிமுறைகள் உள்ளனவா என்ற கேள்வி திறந்திருக்கும் (எடுத்துக்காட்டாக, உள்ளீட்டு ஆயத்தொலைவுகள் ஒரு வரம்புக்குட்பட்ட வரம்பிற்குள் முழு எண்களாக இருக்கும்போது). 1டி க்ளீயின் அளவீட்டு சிக்கலை (இடைவெளிகளின் ஒன்றிணைப்பு) p என்பது அனைத்து இடைவெளிகளையும் குத்துவதற்குத் தேவையான துளையிடும் புள்ளிகளின் எண்ணிக்கையைக் குறிக்கும் இடத்தில் தீர்க்க முடியும் (ஒரு பொதுவான புள்ளியால் துளைக்கப்பட்ட இடைவெளிகளின் ஒன்றிணைப்பை நேரியல் நேரத்தில் உச்சநிலையைக் கணக்கிடுவதன் மூலம் கணக்கிட முடியும்). அளவுரு p என்பது உள்ளீட்டு உள்ளமைவைப் பொறுத்து ஒரு தகவமைப்பு அளவுருவாகும், மேலும் துளையிடும் வழிமுறை க்ளீயின் அளவீட்டு சிக்கலுக்கான தகவமைப்பு வழிமுறையை வழங்குகிறது. கன்வெக்ஸ் தொகுதி தோராயத்தையும் பார்க்கவும், இது குவிந்த உடல்களுக்கான ஒரு திறமையான வழிமுறை குறிப்புகள் மற்றும் மேலும் முக்கியமான ஆவணங்களைப் படிப்பது. . . . . . . இரண்டாம் நிலை இலக்கியம் பிராங்கோ பி. ப்ரிபரேட்டா மற்றும் மைக்கேல் ஐ. ஷாமோஸ் (1985). கணக்கீட்டு வடிவியல் (ஸ்ப்ரிங்கர்-வெர்லாக், பெர்லின்). க்ளீயின் அளவீட்டு சிக்கல், பேராசிரியர் ஜெஃப் எரிக்சனின் கணக்கீட்டு வடிவவியலில் திறந்த சிக்கல்களின் பட்டியலிலிருந்து. (நவம்பர் 8,2005 இல் அணுகப்பட்டது, கடைசி புதுப்பிப்பு ஜூலை 31,1998 இல் இருந்தது.) குறிப்புகள் கணக்கீட்டு வடிவியல் அளவீட்டுக் கோட்பாடு கணித சிக்கல்கள்