கூட்டுத்தொகை பொருந்தும் எண்களைத் தேர்ந்தெடுத்தல், அவற்றை வாசிக்கும் வேகத்திலேயே கிட்டத்தட்ட

யாரும் சொல்லக்கூடிய ஒரு புதிர் இதோ. உங்களிடம் முழு எண்களின் பட்டியல் உள்ளது — எடுத்துக்காட்டாக 3, 9, 14, 20 — ஓர் இலக்கும், எடுத்துக்காட்டாக 23. அவற்றில் சிலவற்றை, அவை இலக்குக்கு சரியாகக் கூடும்படி தேர்ந்தெடுக்க முடியுமா? (இங்கே, முடியும்: 3 + 20 அல்லது 9 + 14.) இதுவே Subset Sum, கணினி அறிவியலின் மிக அடிப்படையான பிரச்சினைகளில் ஒன்று. துல்லியமாகத் தீர்க்கக் கடினமானவை என்று அறியப்பட்ட பிரச்சினைகளின் குடும்பமான ஓர் அடிப்படை NP-முழுமையான (NP-complete) பிரச்சினையாகக் கட்டுரை இதை விவரிக்கிறது.

ஆனால் ஒரு புழைவழி உள்ளது. எண்கள் மிகப் பெரியவை அல்ல என்றால், சாமர்த்தியமான வழிமுறைகள் அவற்றின் அளவைச் சார்ந்த நேரத்தில் இயங்குகின்றன. 1957-இல் பெல்மன் வகுத்த பாரம்பரிய முறை, எண்களின் எண்ணிக்கை n-ஐ இலக்கு t-ஆல் பெருக்கியதற்கு விகிதசமமான நேரத்தை எடுக்கிறது. அன்றுமுதல், வழிமுறைகள் மேம்பட்டுக்கொண்டே வந்துள்ளன:

• பிசிங்கர் (1999): n × N-க்கு விகிதசமம்; இங்கு N மிகப் பெரிய எண்;
• பிரிங்மன் (2017): தோராயமாக n + t;
• பல குழுக்கள் (2021–2024): தோராயமாக n + N^(5/3), பிறகு n + N^(3/2).

தோராயமாக n + N நேரமே புனிதக் கிண்ணமாக இருந்தது — உள்ளீட்டை வாசிப்பதைவிடப் பெரிதாக அதிகமில்லை. இத்துறை ஆய்வாளர்கள் இதை இந்த ஆய்வுப் பாதையின் ‘மிக முக்கியமான திறந்த பிரச்சினை’ என்று அழைத்திருந்தனர்.

இலக்கிலிருந்து மயிரிழை தூரத்தில்

சீனாவின் செஜியாங் பல்கலைக்கழகத்தைச் சேர்ந்த லின் சென், யுசென் மாவோ, குவோச்சுவான் ஜாங் ஆகியோர் n + N^(1+ε) நேரத்தில் இயங்கும் ஒரு வழிமுறையைத் தருகின்றனர்; இங்கு ε முன்கூட்டியே நிர்ணயிக்கப்பட்ட எந்தச் சிறிய நேர்ம எண்ணாகவும் இருக்கலாம் — 0.1, 0.01, 0.001. இது தீர்மானவாதமானது (deterministic), எதிர்ம எண்களையும் மீண்டும் வரும் மதிப்புகளையும் ஏற்கிறது, கணித நிரூபணத்துடன் வருகிறது. ஆசிரியர்கள் இந்த நேரத்தை கிட்டத்தட்ட உகந்தது (near-optimal) என்கின்றனர்.

முடிவு திசையன்களுக்கும் விரிகிறது: பல கூட்டுத்தொகைகள் ஒரே நேரத்தில் தம் இலக்குகளை எட்டும்படி உருப்படிகளைத் தேர்ந்தெடுத்தல், d ஆயத்தொலைவுகளுக்கு N^(d+ε) நேரத்தில். இது, மாறிகள் வரம்புக்குட்பட்ட சமன்பாட்டு அமைப்புகளுக்கு முழுஎண் தீர்வுகளைக் காணும் முழுஎண் நிரலாக்கம் (integer programming) பற்றிப் பல குழுக்கள் எழுப்பிய ஒரு கேள்வியின் ஒரு பகுதிக்கும் விடையளிக்கிறது. இரண்டு விளைவுகள் வெளிப்படையாக வகுக்கப்பட்டுள்ளன: ஓர் எண் தொகுப்பை இரண்டு சம பாதிகளாகப் பிரித்தல், இரண்டு ஒத்த இயந்திரங்களுக்கு இடையே வேலைகளை முடிந்தவரை சமமாகப் பகிர்தல்.

எண்களை உயர் பரிமாணத்துக்கு உயர்த்துதல்

முக்கியக் கருத்து வடிவியல் சார்ந்தது. எண்கள் அடர்த்தியாக இருந்து, இலக்கு சாத்தியமான கூட்டுத்தொகைகளின் வரம்புக்குள் நன்கு அமைந்திருந்தால் பிரச்சினை எளிது என்பது ஏற்கனவே அறியப்பட்டிருந்தது. ஆசிரியர்களின் அவதானிப்பு: ஐதான (sparse) எண் தொகுப்பு ஒன்று, உயர் பரிமாணத்தில் பார்க்கும்போது அடர்த்தியாகத் தோன்றக்கூடும்.

அவர்களின் எடுத்துக்காட்டு {11, 12, 22, 24} என்ற தொகுப்பு. 11, 22 ஆகியவற்றை முதல் அச்சின் வழியே ஒரு படி, இரண்டு படிகள் என்றும், 12, 24 ஆகியவற்றை இரண்டாம் அச்சின் வழியே ஒரு படி, இரண்டு படிகள் என்றும் எழுதுங்கள். அப்போது சாத்தியமான கூட்டுத்தொகைகள் ஒரு சிறிய 4-க்கு-4 சதுரத்தின் ஒவ்வொரு புள்ளியையும் நிரப்புகின்றன. ஆனால் அந்தச் சதுரத்தை மீண்டும் ஒரு கோட்டின் மீது அழுத்தினால் — 11x + 12y-ஐக் கணக்கிட்டு — கூட்டுத்தொகைகள் 0-க்கும் 69-க்கும் இடையே சிதறிய, இடையே இடைவெளிகள் கொண்ட ஏழு தனிக் கொத்துகளாக அமைகின்றன. இடைவெளிகள் வீழலின் (projection) மாயை; இரண்டு பரிமாணங்களில், கட்டமைப்பு எளிமையானது.

கூட்டல் சேர்வியலின் (additive combinatorics) முடிவுகளைப் பயன்படுத்தி, எந்த உள்ளீட்டுக்கும் இத்தகைய உயர் பரிமாண ஆயத்தொலைவுகளை வழிமுறை கட்டமைக்கிறது. ‘நிரம்பிய’ பகுதிக்குள், விடைகள் இலவசமாகக் கிடைக்கின்றன. விளிம்புக்கு அருகே உள்ள ஒரு மெல்லிய மண்டலத்துக்கு மட்டுமே உண்மையான உழைப்பு தேவை; வழிமுறை அதைச் சிறிய பிரச்சினைகளாக உடைத்து மீள்சுழற்சியாக (recursively) தீர்க்கிறது. ஒவ்வொரு சுற்றும் அந்த மண்டலத்தைக் கூர்மையாகச் சுருக்குகிறது; மாறாத எண்ணிக்கையிலான புதிய பரிமாணங்கள் மட்டுமே சேர்க்கப்படுகின்றன.

நிரூபணம் எப்படிக் கட்டப்பட்டது

கட்டுரை ஒரு ‘AI பொறுப்புத் துறப்புடன்’ தொடங்குகிறது. பிரச்சினையின் அடர்த்தியான, பல்பரிமாணப் பதிப்புகள் குறித்த தங்கள் சமீபத்திய பணியை அடிப்படையாகக் கொண்டு, ஆசிரியர்கள் முக்கிய நிரூபணப் பாதையைத் தாமே வடிவமைத்தனர். பிறகு அந்தக் கருத்துகளை முழுமையான கணித நிரூபணங்களாக மாற்ற GPT Astra Ultra என்ற AI மாதிரியைப் பயன்படுத்தினர். அது பல துணைத்தேற்றங்களில் (lemmas) சிக்கிக்கொண்டது; அவை ஆசிரியர்களின் கருத்துகளால் தீர்க்கப்பட்டன; ஒரு பொது ஆய்வுக் குறிப்பு உரையாடல்களை ஆவணப்படுத்துகிறது. அடிப்படைச் சீரற்ற (randomised) வழிமுறை முடிந்ததும், மாதிரி அதை ‘ஆசிரியர்களின் எந்த வழிகாட்டலும் இல்லாமல்’ தீர்மானவாத, பல்பரிமாணப் பதிப்புகளுக்கு விரிவாக்கியது. மாதிரி கட்டுரையின் வரைவையும் எழுதியது; ஆசிரியர்கள் எழுதுவதன்படி, அதன் முக்கிய முடிவுகளை Lean 4 நிரூபண உதவியில் ஒரு நிரூபணத்துடன் சரிபார்த்தது. உள்ளடக்கத்துக்கான முழுப் பொறுப்பையும் ஆசிரியர்கள் ஏற்கின்றனர்.

இன்னும் இறுதிக் கோடு அல்ல

அடுக்கு சரியாக 1 அல்ல, 1 + ε; ε சுருங்கும்போது மறைந்த மாறிலிகள் வளர்கின்றன; பரிமாணங்களின் எண்ணிக்கையைச் சார்ந்திருப்பது உகப்பாக்கப்படவில்லை. ஆசிரியர்களே வழிமுறையை ‘மிகவும் சிக்கலானது’ என்று விவரிக்கின்றனர். கட்டுரை கோட்பாட்டு ரீதியானது: எந்தச் செயலாக்கத்தையோ ஒப்பீட்டுச் சோதனையையோ (benchmark) அது அறிவிக்கவில்லை.