கணினி அறிவியலில் 1962 முதல் நின்ற தடை வீழ்ந்தது
ஹாமில்டோனியன் சுற்று (Hamiltonian cycle) என்பது ஒரு வலையமைப்பின் ஒவ்வொரு புள்ளியையும் சரியாக ஒருமுறை சென்றடைந்து தொடக்கப் புள்ளிக்கே திரும்பும் ஒரு சுற்றுப்பயணம். திசைகொண்ட (directed) வலையமைப்பில், ஒவ்வொரு இணைப்பும் ஒருவழித் தெருவைப் போல ஒரே திசையில் மட்டுமே பின்பற்றக்கூடிய ஓர் அம்புக்குறி. இந்தப் பிரச்சினையின் எடையிடப்பட்ட வடிவம் சமச்சீரற்ற பயண விற்பனையாளர் பிரச்சினை (asymmetric travelling salesman problem) ஆகும்.
அத்தகைய சுற்று இருக்கிறதா என்று தீர்மானிப்பது பாடநூல்களில் இடம்பெறும் ஒரு கடினப் பிரச்சினை. 1962 இல், ரிச்சர்ட் பெல்மனும், அவரிடமிருந்து தனித்து மைக்கேல் ஹெல்டு, ரிச்சர்ட் கார்ப் ஆகியோரும், n புள்ளிகள் கொண்ட வலையமைப்புக்கு இதைச் சுமார் 2ⁿ நேரத்தில் (பல்லுறுப்புக்கோவை அளவில் மட்டுமே வளரும் காரணிகள் நீங்கலாக) தீர்க்கும் இயக்கவியல் நிரலாக்க (dynamic programming) வழிமுறைகளை வழங்கினர். அறுபது ஆண்டுகளுக்கும் மேலாக, பொதுவான திசைகொண்ட வலையமைப்புகளில் யாராலும் அடிப்படையிலேயே இதைவிடச் சிறப்பாகச் செய்ய முடியவில்லை.
திசையற்ற உறவினர் ஏற்கெனவே வீழ்ந்திருந்தது
இருவழி இணைப்புகள் கொண்ட வலையமைப்புகளுக்கு, ஆண்ட்ரியாஸ் பியோர்க்லண்ட் 2014 இல் 1.657ⁿ நேரத்தில் இயங்கும் ஒரு சீரற்ற வழிமுறை மூலம் அந்தத் தடையை உடைத்தார்; ஆய்வுக்கட்டுரையின்படி, இந்தப் பணி அவருக்கு 2016 EATCS–IPEC நெரோடு பரிசைப் பெற்றுத் தந்தது. பொதுவான திசையற்ற வலையமைப்புகளுக்கு அறியப்பட்டவற்றில் இதுவே இன்றும் மிக வேகமானது. திசைகொண்டவற்றுக்கு, முன்னேற்றம் சிறப்பு நிலைகளில் மட்டுமே — இருபிரிவு (bipartite) வலையமைப்புகள், ஒவ்வொரு புள்ளிக்கும் குறைவான இணைப்புகள் கொண்ட வலையமைப்புகள் — அல்லது நிரூபிக்கப்படாத ஒரு கருதுகோளான ஸ்ட்ராசனின் அணுகுமுறைத் தரவரிசை ஊகத்தின் (asymptotic rank conjecture) கீழ் மட்டுமே வந்தது.
புதிய எல்லை
டோக்கியோ பல்கலைக்கழகத்தைச் சேர்ந்த டொமோஹிரோ கோஆனா, டோக்கியோ நிறுவனமான CyberAgent ஐச் சேர்ந்த சோ குமாபே ஆகியோர் இப்போது திசைகொண்ட பிரச்சினையைப் பின்வரும் நேரத்தில் தீர்மானிக்கும் ஒரு சீரற்ற வழிமுறையை வழங்குகின்றனர்:
O((375/196)ⁿ) = O(1.9133ⁿ)**.
பொதுவான திசைகொண்ட வலையமைப்புகளுக்கு, 1962 முதல் அடுக்குக்குறியின் அடியில் (base of the exponential) கிடைத்த முதல் முன்னேற்றம் இதுவே.
ஒற்றைப்படை, இரட்டைப்படையில் எண்ணுதல்
சிக்கல் நுட்பமானது. சுற்றுகளை மாடுலோ 2 இல் எண்ணுவது — அவற்றின் எண்ணிக்கை ஒற்றைப்படையா இரட்டைப்படையா என்பதை மட்டும் அறிவது — ஏற்கெனவே 2ⁿ க்குக் கீழே சாத்தியமாக இருந்தது. ஆனால் பூஜ்ஜியமற்ற இரட்டைப்படை எண்ணிக்கையிலான சுற்றுகள் பூஜ்ஜியத்தைப் போலவே தோற்றமளிக்கின்றன. வழக்கமான தீர்வு, இணைப்புகளுக்குச் சீரற்ற எடைகளைக் கொடுப்பது; அப்போது ஏதேனும் ஒரு மொத்த எடையில் ஒரு தீர்வு தனித்துவமானதாகிறது (தனிமைப்படுத்தல் துணைத்தேற்றம், isolation lemma). ஆனால் வேகமான ஒற்றை-இரட்டை எண்ணும் முறையால் எடைகளைக் கையாள முடியவில்லை.
ஆசிரியர்களின் செய்முறை, எளிய சொற்களில்:
- சுற்றின் ஓர் அம்புக்குறியை ஊகித்து, அதற்குப் பதிலாக அந்த அம்புக்குறியின் ஒரு முனையிலிருந்து மறு முனைக்கு ஒவ்வொரு புள்ளியையும் கடந்து செல்லும் ஒரு பாதையைத் தேடுவது.
- ஒவ்வொரு அம்புக்குறியையும் 1/50 நிகழ்தகவுடன் சீரற்ற முறையில் நீக்குவது.
- ஒவ்வொரு புள்ளியிலும் உள்வரும் அம்புக்குறிகளின் மூன்று குழுக்களை உருவாக்கி, எஞ்சிய ஒவ்வொரு அம்புக்குறியையும் சீரற்ற முறையில் தேர்ந்த, வெறுமையற்ற குழுத் தொகுப்பில் நகலெடுப்பது.
- சுற்றுப்பயணம் இருந்தால், குறைந்தது (49/50)ⁿ⁻¹ நிகழ்தகவுடன், செல்லுபடியாகும் பாதைகளின் எண்ணிக்கை ஒற்றைப்படையாக இருக்கும்படி ஒவ்வொரு புள்ளிக்கும் ஒரு குழுவைத் தேர்ந்தெடுக்க முடியும்.
- ஒவ்வொரு அம்புக்குறிக்கும் அல்லாமல், ஒவ்வொரு குழுவுக்கும் ஒரு சீரற்ற எடையைக் கொடுப்பது. இப்போது தனிமைப்படுத்தல் உத்தி வேலை செய்கிறது; சுமார் (50/49)ⁿ மறுநிகழ்வுகள் போதுமானவை.
- ஒவ்வொரு மறுநிகழ்வும், பியோர்க்லண்ட், காஸ்கி, கௌட்டிஸ் ஆகியோரின் அணிக்கோவைகளின் (matrix determinants) கூட்டுத்தொகைகளையும், அர்விந்த், குருசுவாமி ஆகியோரும் பயன்படுத்திய ஒரு சீரற்ற “நேர்கோட்டாக்கத்தையும்” (linearisation) கொண்டு, ஒவ்வொரு மொத்த எடையிலும் ஒற்றை-இரட்டை எண்ணிக்கைகளை (15/8)ⁿ நேரத்தில் கணக்கிடுகிறது.
இரண்டையும் பெருக்கினால்: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ.
ஓர் இயந்திரம் உருவாக்கிய நிரூபணம்
ஆய்வுக்கட்டுரை உருவாக்க AI குறித்த ஓர் அறிவிப்புடன் முடிகிறது: முதன்மைத் தேற்றத்தின் நிரூபணத்தை ChatGPT 6 Astra உருவாக்கியது; கையெழுத்துப் படியை வரைவதிலும் அது உதவியது. ஆசிரியர்கள் இடைநிலை முன்மொழிவுகளின் கூற்றுகளை வழங்கினர் — அவை மாதிரியின் மூலத் தீர்வுக்கு ஒரு சேர்வியல் (combinatorial) விளக்கத்தைத் தருகின்றன — பின்னர் அனைத்தையும் சரிபார்த்துத் திருத்தி, முழுப் பொறுப்பையும் ஏற்கின்றனர்.
இந்த முடிவு கோட்பாட்டு ரீதியானது — எந்த நிரலும் இயக்கப்படவில்லை — மேலும் வழிமுறை சீரற்றது; இரு திசைகளிலும் பிழைக்குச் சிறிய வாய்ப்பு உண்டு. ஒருவழித் தெருக்களுக்கான 1.9133 க்கும் இருவழித் தெருக்களுக்கான 1.657 க்கும் இடையே, ஒரு பெரிய இடைவெளி இன்னும் திறந்தே உள்ளது.
