கிளிக்குகளைக் கண்டறிவதற்கான வேக வரம்பு 40 ஆண்டுகளுக்குப் பிறகு வீழ்கிறது
n பேர் கொண்ட ஒரு சமூக வலைப்பின்னலைக் கற்பனை செய்யுங்கள். அவர்களில், அனைவரும் ஒருவரையொருவர் அறிந்த k பேர் கொண்ட ஒரு குழு உள்ளதா? கணினி அறிவியலாளர்கள் அப்படிப்பட்ட குழுவை ஒரு k-கிளிக் (k-clique) என்று அழைக்கின்றனர்; ஒன்றைக் கண்டறிவது எண்ணற்ற பயன்பாடுகள் கொண்ட ஒரு மரபார்ந்த சிக்கல். எளிமையான அணுகுமுறை, k பேர் கொண்ட சாத்தியமான ஒவ்வொரு குழுவையும் சரிபார்க்கிறது — தோராயமாக n^k குழுக்கள் — பெரிய வலைப்பின்னல்களுக்கு இது நம்பிக்கையற்றது.
1985-இன் ஓர் உத்தியும் ஒரு நீண்ட சவாலும்
40-க்கும் மேற்பட்ட ஆண்டுகளுக்கு முன்பு, Jaroslav Nešetřil, Svatopluk Poljak ஆகியோர் ஒரு குறுக்குவழியைக் கண்டறிந்தனர். k-கிளிக்கைத் தேடுவதை, ஒரு பெரிய வரைபடத்தில் (graph) ஒரு முக்கோணத்தைத் தேடுவதாக அவர்கள் மாற்றினர்; அதையோ, எண்களின் பெரிய அட்டவணைகளான அணிகளைப் பெருக்குவதன் (multiplying matrices) மூலம் செய்ய முடியும். செலவு, அணிப் பெருக்கலின் அடுக்குக்குறியான (exponent) ω-வைச் சார்ந்தது: அவர்களின் முறைக்குச் சுமார் n^(ωk/3) படிகள் ஆகின்றன. ω-வின் துல்லியமான மதிப்பு யாருக்கும் தெரியாது. அது குறைந்தது 2; கட்டுரை சமீபத்திய ஒரு மேல் வரம்பாக 9/4-ஐக் குறிப்பிடுகிறது.
1985-இன் அந்த முறையின் அடுக்குக்குறி ஒருபோதும் முறியடிக்கப்படவில்லை. 2004-இல், ஏதேனும் ஒரு நிலையான k-க்கு இதைவிடச் சிறப்பாகச் செய்யுமாறு Gerhard Woeginger ஆய்வாளர்களுக்குச் சவால் விடுத்தார்; இருபது ஆண்டுகளுக்கும் மேல் கடந்தன. இதற்கிடையில், k-கிளிக் கருதுகோள் (k-Clique Hypothesis) — n^(ωk/3) என்பதே அடிப்படையில் சாத்தியமான மிகச் சிறந்தது என்பது — “நுண்ணளவுச் சிக்கலியலின்” (fine-grained complexity) ஓர் அடித்தளமாக ஆனது. இலக்கணங்களைப் பகுப்பாய்வு செய்வது (parsing) முதல் சுருக்கப்பட்ட தரவைப் பகுப்பாய்வு செய்வது வரை, வேறு பல சிக்கல்களையும் வேகமாகத் தீர்க்க முடியாது என்று வாதிட ஆய்வாளர்கள் அதைப் பயன்படுத்தினர்.
நகரும் ஓர் இலக்கு
இந்தக் கருதுகோளை மறுப்பதில் ஒரு தனிச் சிரமம் இருந்தது. அது முன்கணிக்கும் செலவு, அறியப்படாத ω-வைச் சார்ந்தது. ω-வின் இன்றைய சிறந்த மதிப்பை முறியடிக்கும் ஒரு வழிமுறை (algorithm), பின்னாளில் யாராவது வேகமான அணிப் பெருக்கலைக் கண்டறிந்தால், கருதுகோளை முறியடிப்பதை நிறுத்திவிடக்கூடும்.
MIT-ஐச் சேர்ந்த Virginia Vassilevska Williams, டெல் அவீவ் பல்கலைக்கழகத்தைச் (Tel Aviv University) சேர்ந்த Or Zamir ஆகியோர் இந்தச் சிக்கலைத் தவிர்த்துச் செல்கின்றனர். போதுமான அளவு பெரிய ஒவ்வொரு k-க்கும், ஒரு k-கிளிக்கைச் சுமார் n^((ω/3 − c)k) படிகளில் கண்டறிய — எண்ணவும்கூட — முடியும் என்று அவர்கள் நிரூபிக்கின்றனர்; இங்கு c என்பது k-ஐயோ ω-வையோ சாராத ஒரு நேர்ம மாறிலி. சேமிப்பு, ω-வின் உண்மையான மதிப்புக்கு எதிராக அளக்கப்படுகிறது — அது எதுவாக இருந்தாலும். கற்பனை செய்யக்கூடிய மிகச் சிறந்த நிலையான ω = 2 ஆனாலும் அது நீடிக்கிறது.
ஓர் ஆப்பை மடித்தல்
முறையின் மையம், ஒன்பது உச்சிகள் (vertices) கொண்ட வடிவங்களைப் பற்றியது. நிலையான அணுகுமுறை அவற்றை மூன்று பேர் கொண்ட மூன்று குழுக்களாகப் பிரித்து, மூன்று பிரம்மாண்டமான அணிகளைப் பெருக்குகிறது. ஆசிரியர்கள் ஓர் ஆப்பைப் (wedge) — ஓர் உச்சியைப் பகிர்ந்துகொள்ளும் இரண்டு விளிம்புகள் (edges) — கவனிக்கின்றனர்; இரண்டு அணிகளுக்கு இடையே, எதையும் மாற்றாத ஓர் அட்டவணையை — அலகு அணியை (identity) — செருகுகின்றனர். பிறகு அந்த அலகு அணியைச் சில “இடமாற்றங்களின்” (swaps) கூட்டுத்தொகையாக எழுதுகின்றனர் — அவை ஒவ்வொன்றும் ஆப்பின் இரண்டு விளிம்புகளையும் ஒன்றாக இணைக்கிறது — அதனுடன் குறைந்த தரம் (low rank) கொண்ட ஒரு மீதியும்.
இடமாற்றங்கள், குறைவான விளிம்புகள் கொண்ட எளிய வடிவங்களைத் தருகின்றன; அவை மீண்டும் அதே முறையால் கையாளப்படுகின்றன; ஒன்பது உச்சிகள் கொண்ட ஒரு வடிவத்தில் அதிகபட்சம் 36 விளிம்புகளே இருப்பதால், மீள்சுழற்சி (recursion) முடிவுக்கு வருகிறது. குறைந்த தரம் கொண்ட மீதி, பெருக்க வேண்டிய அணிகளைச் சுருக்குகிறது. ω = 2 ஆனாலும் ஓர் ஆதாயத்தைத் தக்கவைப்பது, இந்த உத்தியைத் தனித்தனியான இரண்டு ஆப்புகளுக்கு ஒரே நேரத்தில் பயன்படுத்துவதுதான். ஒன்பதின் மடங்காக உள்ள எந்த k-ஐயும் பிறகு ஒன்பது தொகுதிகளாகக் குழுவாக்கலாம்.
உண்மையானது, ஆனால் மிகச் சிறியது
ஆசிரியர்கள் ஆதாயத்துக்கு எண்களைத் தரவில்லை. மாறிலிகள் “உகப்பாக்கம் இல்லாமல் மிக மிக நுண்ணியது முதல், கணிசமான உகப்பாக்கங்களுடன் மிகச் சிறியது வரை” இருப்பதாக அவர்கள் விவரிக்கின்றனர். நடைமுறை வேகம் இதன் நோக்கமல்ல: பல பத்தாண்டுகளாக நம்பப்பட்ட ஒரு தடை இல்லவே இல்லை என்பதே.
விளைவுகள் கிளிக்குகளையும் தாண்டிச் செல்கின்றன. n மாறிகளுக்குச் சுமார் 2^(ωn/3) படிகளில் இயங்கிய, Max-Cut, Max-2-SAT போன்ற கடினமான உகப்பாக்கச் சிக்கல்களுக்கான துல்லியமான வழிமுறைகளும் இப்போது ஒரு சிறிய அடுக்குக்குறியைப் பெறுகின்றன. எந்தவொரு நிலையான சிறிய வரைபடத்தின் நகல்களை எண்ணுவதும் அவ்வாறே.
AI செய்தது என்ன
ஒரு தனிப் பிரிவில், பொது இணைய இடைமுகம் வழியாகப் பயன்படுத்தப்பட்ட ChatGPT-6-உடன் தாங்கள் எவ்வாறு பணியாற்றினர் என்பதை ஆசிரியர்கள் விவரிக்கின்றனர். ஐந்து பேர் கொண்ட கிளிக்குகளுக்கான அவர்களின் சொந்த யோசனைகளிலிருந்தும், மற்றொரு அனுமானமான அடுக்குக்குறி நேரக் கருதுகோளை (Exponential Time Hypothesis) மறுக்கும் சமீபத்திய ஒரு OpenAI முடிவிலிருந்தும் தொடங்கி, இந்த மாதிரி 5-கிளிக்குகளுக்கு முதல், சிக்கலான ஒரு மேம்பாட்டைக் கண்டறிந்தது. பிறகு ஆசிரியர்கள், AI-இன் உதவியுடன், அதை நிரூபணத்தின் மையத்தில் உள்ள இயற்கணிதப் பிரிப்பாக (algebraic decomposition) வடித்தெடுத்தனர்; அதை அவர்கள் “கிட்டத்தட்ட முழுமையாக AI-இன் பங்களிப்பு” என்று கருதுகின்றனர். அதைச் சுற்றிக் கட்டப்பட்ட வழிமுறைக் கட்டமைப்பு முக்கியமாகத் தங்களுடையது என்கின்றனர்.
ஒரு குறிப்பு தனித்து நிற்கிறது. AI உருவாக்கிய தெளிவற்ற நிரூபணங்கள் மனிதர்கள் படிப்பதற்குக் கடினமானவை என்று ஆசிரியர்கள் குறிப்பிடுகின்றனர் — மேலும் அவை “AI-க்கே புரிந்துகொள்வதற்குக் கடினமானவை என்பதைக் கண்டு அவர்கள் வியந்தனர்”.
