தடைசெய்யப்பட்ட ஒப்பீடுகளுடன் வரிசைப்படுத்தல், கிட்டத்தட்ட அதே வேகத்தில்
n உருப்படிகளை இரண்டிரண்டாக ஒப்பிட்டு வரிசைப்படுத்த, ஏறக்குறைய n log n ஒப்பீடுகள் அவசியமும், போதுமானவையும் ஆகும். ஆனால் அது, எந்த இரண்டு உருப்படிகளையும் ஒப்பிட முடியும் என்று அனுமானிக்கிறது.
பெரும்பாலும் அது முடிவதில்லை. ஆசிரியர்கள் 2011-ஆம் ஆண்டு ஆய்வுக் கட்டுரை ஒன்றிலிருந்து ஓர் எடுத்துக்காட்டைக் கடன் வாங்குகின்றனர்: ஒரே வேலைக்குப் பல விண்ணப்பதாரர்கள் விண்ணப்பிக்கின்றனர், ஒவ்வொருவருக்கும் பரிந்துரையாளர்கள் உண்டு. ஏதேனும் ஒரு பரிந்துரையாளருக்கு இருவரையும் தெரிந்தால் மட்டுமே இரண்டு விண்ணப்பதாரர்களை ஒப்பிட முடியும். அனுமதிக்கப்பட்ட ஒப்பீடுகள் ஒரு வலைப்பின்னலை, ஒரு வரைபடத்தை (graph) உருவாக்குகின்றன: ஒவ்வொரு உருப்படியும் ஒரு புள்ளி, அனுமதிக்கப்பட்ட ஒவ்வொரு ஒப்பீடும் ஓர் இணைப்பு. உண்மையான வரிசை மறைந்திருக்கிறது; ஆனால் வரைபடம் அதை, ஒவ்வொரு உருப்படியையும் அடுத்ததுடன் இணைக்கும் ஒரு பாதையாகக் கொண்டிருக்கும் என்பது உறுதி. கேள்வி: வரிசையை மீட்டெடுக்க எத்தனை ஒப்பீடுகள் தேவை? இதுவே பொதுமைப்படுத்தப்பட்ட வரிசைப்படுத்தல் (generalized sorting).
வழக்கமான உத்திகள் ஏன் தோற்கின்றன
பாரம்பரிய வழிமுறைகள் தேர்வுச் சுதந்திரத்தைச் சார்ந்துள்ளன. QuickSort ஒரு “மைய உருப்படியை” (pivot) தேர்ந்தெடுத்து, அதைப் பெரும்பாலான பிற உருப்படிகளுடன் ஒப்பிடுகிறது; ஆனால் தன்னிச்சையான ஒரு வரைபடத்தில், பெரும்பாலான பிற உருப்படிகளுடன் இணைக்கப்பட்ட உருப்படி எதுவும் இல்லாமல் போகலாம். MergeSort உருப்படிகளைக் குழுக்களாகப் பிரித்து ஒவ்வொன்றையும் வரிசைப்படுத்துகிறது; ஆனால் ஒரு குழுவைத் தனியாக வரிசைப்படுத்த முடியாமல் போகலாம்: இறுதி வரிசையில் அடுத்தடுத்து வரும் இரண்டு உருப்படிகள் அந்தக் குழுவுக்குள் இணைக்கப்பட்டிருக்க வேண்டியதில்லை. இன்னும் அடிப்படையாக, சாதாரண வரிசைப்படுத்தலில், சாத்தியமான வரிசைகளில் கணிசமான பங்கை விலக்கும் ஓர் ஒப்பீடு எப்போதும் கிடைக்கிறது; கட்டுப்படுத்தப்பட்ட ஒப்பீடுகளுடன், அப்படி எதுவும் இல்லாமல் போகலாம்.
முன்னேற்றம் மெதுவாக இருந்தது. 2011-இல், Zhiyi Huang, Sampath Kannan, Sanjeev Khanna ஆகியோர், மடக்கைக் காரணிகள் (logarithmic factors) தவிர்த்து, ஏறக்குறைய n¹·⁵ ஒப்பீடுகளைப் பயன்படுத்தும் ஒரு முறையைக் கண்டனர்; அன்று முதல், தன்னிச்சையான வரைபடங்களுக்கு அந்த வரம்பே நிலைத்திருந்தது. இந்தச் சிக்கல் சாதாரண வரிசைப்படுத்தலை விட அடிப்படையிலேயே கடினமானதாக, அதாவது 1-க்கு மேற்பட்ட ஓர் அடுக்குக்கு உயர்த்தப்பட்ட n தேவைப்படுவதாக, இருக்கக்கூடுமா என்றுகூட அவர்கள் கேட்டனர்.
முதலில் முன்கணிப்பு, பிறகு சீரமைப்பு
New York University-ஐச் சேர்ந்த Sanjeev Khanna, Harvard University-ஐச் சேர்ந்த Aaron Putterman, அதே New York University-ஐச் சேர்ந்த Junkai Song ஆகியோர் இப்போது அந்தக் கேள்விக்குப் பதில் அளிக்கின்றனர்: இல்லை. அவர்களின் சீரற்ற (randomised) வழிமுறை, எந்த வரைபடத்திலும், சராசரியாக ஏறக்குறைய n log⁴ n ஒப்பீடுகளில் வரிசைப்படுத்துகிறது — சாதாரண வரிசைப்படுத்தலை விடச் சில மடக்கைக் காரணிகள் மட்டுமே அதிகம். மேலும், அது “ஒப்பீட்டளவில் எளிமையானது” என்று அவர்கள் எழுதுகின்றனர். ஆனால் இந்த ஆதாயம் கோட்பாட்டு ரீதியானது: நிரூபணத்தின் மாறிலிகள் மிகப் பெரியவை (2³² போன்ற காரணிகள்); எனவே மிகப் பெரிய n-க்கு மட்டுமே அனுகூலம் வெளிப்படுகிறது.
இது அறியப்பட்ட ஒரு முடிவின் மீது கட்டப்பட்டுள்ளது: ஒவ்வோர் இணைப்பின் திசை குறித்தும், அவற்றில் w இணைப்புகளில் தவறான ஓர் ஊகத்தை யாராவது உங்களிடம் தந்தால், ஏறக்குறைய n log n + w ஒப்பீடுகளில் வரிசையை மீட்டெடுக்க முடியும். எனவே பணி, குறைவான ஒப்பீடுகளைக் கொண்டு, குறைவான பிழைகள் உள்ள ஓர் ஊகத்தை உருவாக்குவதாக மாறுகிறது. முக்கியப் படிகள்:
- தோராயமான முதல் ஊகம். இணைக்கப்பட்ட ஜோடிகளின் ஒரு சீரற்ற மாதிரியை (random sample) ஒப்பிட்டு, பதில்களுடன் ஒத்துப்போகும் ஏதேனும் ஒரு வரிசையைத் தேர்ந்தெடுக்கவும். அது பல பிழைகளைச் செய்கிறது, ஆனால் மிக அதிகமாக அல்ல.
- பிழைகளைத் திருத்துவதற்குப் பதிலாக, தனிமைப்படுத்து. தவறான ஊகங்களைச் சரிசெய்வதற்குப் பதிலாக, வழிமுறை, சராசரியை விடப் பிழைகள் அடர்த்தியாக உள்ள வரைபடப் பகுதிகளைக் கண்டறிந்து அவற்றை ஒதுக்கி வைக்கிறது. ஒவ்வொரு சுற்றும், எதிர்பார்ப்பு அளவில் (in expectation), மீதமுள்ள பிழைகளை நான்கில் ஒரு பங்காகக் குறைக்கிறது.
- பிறகு திரும்பி வா. ஒதுக்கி வைக்கப்பட்ட இணைப்புகள் பிந்தைய ஒரு கட்டத்தில் கையாளப்படுகின்றன. ஒவ்வொரு கட்டமும், இன்னும் நிலுவையில் உள்ள இணைப்புகளில் குறைந்தது பாதியைத் தீர்க்கிறது; எனவே ஒரு மில்லியன் இணைப்புகளுக்கு ஏறக்குறைய இருபது கட்டங்கள் போதும்.
இயந்திரங்களின் துணையுடன் கண்டறியப்பட்ட ஒரு நிரூபணம்
ஆய்வுக் கட்டுரையின் AI வெளிப்படுத்தல் அறிக்கை வழக்கத்துக்கு மாறாக விரிவானது. மேம்படுத்தப்பட்ட வரம்புகளை நிரூபிப்பதில் ChatGPT 6-Astra “இன்றியமையாததாக இருந்தது” என்று அது கூறுகிறது. ஒரு மாதிரி (model) முதலில் ஏறக்குறைய n¹·³³ ஒப்பீடுகளைப் பயன்படுத்தும் ஒரு வழிமுறையைக் கண்டது, பிறகு தேங்கியது. ஆசிரியர்கள் அதை n¹·²-க்குக் கொண்டு சென்றனர்; பிறகு, பல வாரங்களில் டஜன் கணக்கான முறை தூண்டப்பட்டு (prompted), மாதிரிகள் அடுத்தடுத்த மேம்பாடுகளைக் கண்டன — n^(10/9), n^(17/16), n^(19/18) — இறுதியில் கிட்டத்தட்ட நேரியல் (near-linear) வழிமுறையை எட்டின. அந்த இறுதிக் கண்டுபிடிப்புக்குத் தங்களின் சொந்த இடைநிலைப் படி இன்றியமையாததாக இருந்ததா என்பது தெளிவாக இல்லை என்றும் ஆசிரியர்கள் சேர்க்கின்றனர்.
இன்னும் திறந்திருப்பவை
இந்த முடிவு கணினி நேரத்தை அல்ல, ஒப்பீடுகளையே கணக்கிடுகிறது: கூறப்பட்டுள்ளபடி, இந்த வழிமுறை பல்லுறுப்புக்கோவை (polynomial) நேரத்தில் இயங்குவதில்லை, ஆனால் 2011 முறை அப்படி இயங்கியது. ஆசிரியர்கள் மூன்று திறந்த கேள்விகளைப் பட்டியலிடுகின்றனர்: மீதமுள்ள மடக்கைக் காரணிகளை அகற்ற முடியுமா, சீரற்ற தன்மை இல்லாத ஒரு வழிமுறையும் அதே அளவு சிறப்பாகச் செயல்பட முடியுமா, திறமையான ஒரு வழிமுறை அதே எண்ணிக்கையிலான ஒப்பீடுகளை எட்ட முடியுமா — அல்லது n¹·⁵-ஐ முறியடிக்கவாவது முடியுமா.
