கணினியியல் & செயற்கை நுண்ணறிவுமுன்பதிப்புகோட்பாடுபடிக்க 3 நிமிடங்கள்

மாபெரும் ரூபிக் கனசதுரங்களுக்கு, 10⁴⁰ மாறிலி 30.5-ஆகக் குறைப்பு

இப்போதுதான் 50 வயதை எட்டிய ரூபிக் கனசதுரம் (Rubik’s Cube), உலகிலேயே மிகப் பிரபலமான புதிராக இருக்கலாம்; அதன் மையக் கேள்விகளில் ஒன்றைச் சொல்வது எளிது: மிக மோசமான நிலையில், அதைத் தீர்க்க எத்தனை நகர்வுகள் தேவை? பாரம்பரிய 3×3×3 கனசதுரத்துக்கு, விடை துல்லியமாகத் தெரியும்: 20 நகர்வுகள்; இந்தப் புதிய ஆய்வுக் கட்டுரையின் ஆசிரியர்களில் ஒருவரான Tomas Rokicki-ஐ உள்ளடக்கிய ஒரு குழு 2014-இல் வெளியிட்ட முடிவு இது.

ஒவ்வொரு விளிம்பின் நெடுகிலும் n அடுக்குகள் கொண்ட பெரிய கனசதுரங்களுக்கு, துல்லியமான விடை எட்டாத தொலைவில் உள்ளது — கொடுக்கப்பட்ட ஒரு n×n×n கனசதுரத்தை உகந்த முறையில் (optimally) தீர்ப்பது NP-முழுமையானதும் (NP-complete) கூட. ஆனால் 2011-இல், Erik Demaine-உம் சக ஆய்வாளர்களும், மிக மோசமான நிலை எவ்வாறு வளர்கிறது என்பதைக் காட்டினர்: n² / lg n-க்கு நேர்விகிதத்தில்; இங்கே lg என்பது அடிமானம் 2 கொண்ட மடக்கை. இது, அடிப்படையில் துண்டுகளை ஒவ்வொன்றாகத் தீர்க்கும் வழக்கமான முறைகளை விட, ஒரு மடக்கைக் காரணி அளவுக்குச் சிறந்தது.

அபத்தமான மாறிலி கொண்ட ஒரு நிரூபணம்

ஆனால் ஒரு சிக்கல் இருந்தது. 2011 முடிவு வளர்ச்சி வீதத்துக்கு உத்தரவாதம் அளித்தது, அதன் முன் உள்ள எண்ணுக்கு அல்ல. அந்த வழிமுறையை (algorithm) விரிவாகப் பின்தொடர்ந்தபோது, அதன் மாறிலி ஏறக்குறைய 1.01 × 10⁴⁰ என்று ஆசிரியர்கள் கண்டறிகின்றனர். குற்றவாளி, ஒரு கணினிச் சரிபார்ப்பு: 24 துண்டுகள் கொண்ட ஒரு குழுவின் ஒவ்வோர் அமைப்பையும் சில நகர்வுகளால் எட்ட முடியும் என்று அது நிரூபித்தது, ஆனால் எவ்வளவு விரைவாக என்று சொல்லவில்லை. அந்த நீளத்துக்குப் பாதுகாப்பான ஒரே வரம்பு, அந்த அமைப்புகளின் குழுவின் அளவு, ஏறக்குறைய 3.1 × 10²³ படிகள்; சூத்திரம் இறுதியில் 24! (1 × 2 × … × 24, ஏறக்குறைய 6.2 × 10²³) என்ற மிகப் பெரிய எண்ணை இரண்டு இடங்களில் பயன்படுத்துகிறது. மாறாக, கீழ் வரம்பு (lower bound) — கலைக்கப்பட்ட கிட்டத்தட்ட ஒவ்வொரு கனசதுரத்துக்கும் தேவைப்படும் நகர்வுகளின் எண்ணிக்கை — ஏறக்குறைய 12.88 என்ற அடக்கமான மாறிலியைக் கொண்டுள்ளது. எனவே, நியாயமான அளவுகளுக்கு அத்தகைய வழிமுறை ஒருபோதும் நடைமுறைக்கு உகந்ததாக இருக்க முடியாது என்று இந்தச் சமூகத்தில் பலர் நம்பினர்.

MIT, TU Munich, Palo Alto ஆகியவற்றைச் சேர்ந்த Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf, Erik Demaine ஆகியோர், இப்போது அந்த மாறிலியை வெளிப்படையானதாகவும் சிறியதாகவும் ஆக்கியுள்ளனர்.

கனசதுரத் துண்டுகளுக்கான வரிசைப்படுத்தும் வலைப்பின்னல்கள்

பெரிய கனசதுரத்தில், மையத் துண்டுகளே ஆதிக்கம் செலுத்துகின்றன: அவற்றின் எண்ணிக்கை n²-ஆக வளர்கிறது, அதே நேரம் மூலைகளும் விளிம்புகளும் n-க்கு நேர்விகிதமான உறுப்புகளை மட்டுமே சேர்க்கின்றன. மையத் துண்டுகள் 24 கொண்ட குடும்பங்களாகப் பிரிகின்றன; அவை தமக்குள் மட்டுமே இடம் மாற முடியும். அடிப்படைக் கருவி பரிமாற்றி (commutator): A B A′ B′ என்ற வடிவிலான ஒரு நகர்வு வரிசை; அது கிட்டத்தட்ட எல்லாவற்றையும் இடம் மாற்றாமல் விட்டு, ஒரு குடும்பத்தின் மூன்று துண்டுகளை மட்டும் இடம் மாற்றுகிறது. பயன்படுத்தக்கூடிய 4,000 மூன்று-துண்டு இடமாற்றங்கள் அனைத்துக்குமான நகர்வு வரிசைகளைக் குழு கண்டறிந்தது; ஒவ்வொன்றும் அதிகபட்சம் 12 நகர்வுகள் நீளம்.

இரண்டு யோசனைகள் எண்ணிக்கையைக் குறைக்கின்றன. முதலாவது, ஒரே பரிமாற்றியை, கிடை வரிசைகள், நெடுவரிசைகளின் முழுக் குழுக்கள் முழுவதும், பல குடும்பங்களுக்கு ஒரே நேரத்தில் பயன்படுத்தலாம். இரண்டாவது, ஒவ்வொரு குடும்பத்தையும் தனித்தனியாகத் தீர்ப்பதற்குப் பதிலாக, ஒவ்வொரு குடும்பமும் இடமாற்றங்களின் நிலையான ஒரே பொது வரிசையைப் (universal sequence) பின்பற்றுகிறது; தனக்குத் தேவையில்லாதவற்றை அது வெறுமனே தவிர்த்துவிடுகிறது. ஒரு துணைத்தேற்றம் (lemma) அனைத்தையும் இணைக்கிறது: L கட்டங்கள் கொண்ட ஒரு பொது வரிசை, L/2 என்ற முதன்மை மாறிலியைத் தருகிறது.

அந்த வரிசையைச் சுருக்க, கணினி அறிவியலின் வரிசைப்படுத்தும் வலைப்பின்னல்களிடமிருந்து (sorting networks) கருவிகள் கடன் வாங்கப்படுகின்றன: எந்த உள்ளீட்டையும் வரிசைப்படுத்தும், ஒப்பீடுகளின் நிலையான அமைப்புகள் அவை. ஆறு உள்ளீடுகள் கொண்ட உகந்த வரிசைப்படுத்தும் வலைப்பின்னல் 96 கட்டங்களைத் தருகிறது, எனவே 48 என்ற மாறிலி. 24 நிலைகளை 12-இன் குழுக்களாகவும், பின்னர் 4-இன் குழுக்களாகவும் பிரிக்கும், கணினித் தேடலால் கண்டறியப்பட்ட வலைப்பின்னல்கள், அதை 72 கட்டங்களுக்கு (36) கொண்டு வருகின்றன. இறுதியாக, ஒரே நேரத்தில் மூன்றுக்கும் மேற்பட்ட துண்டுகளைக் கலைக்கும் நகர்வுகளை அனுமதித்து, நிலைகளை வேறு விதமாகப் பிரிப்பது, அதை 61 கட்டங்களுக்குக் கொண்டு வருகிறது.

முப்பது புள்ளி ஐந்து

தேற்றம்: எந்த n×n×n கனசதுரத்தையும் அதிகபட்சம் 30.5 n²/lg n நகர்வுகளில் தீர்க்க முடியும், கூடுதலாகப் பெரிய n-க்குப் புறக்கணிக்கத்தக்கதாக மாறும் உறுப்புகள். மாறிலி 3.30 × 10³⁸-க்கும் அதிகமான காரணியால் மேம்படுகிறது; அது கீழ் வரம்பின் 2.37 என்ற காரணிக்குள் (30.5 / 12.88) அமைகிறது. முன்னோட்டப் பயிற்சியாகப் (warm-up) பயன்படுத்தப்பட்ட தட்டையான n×n×1 பதிப்புக்கு, மாறிலி 12 அல்லது 18-இலிருந்து 1.5-ஆகக் குறைகிறது.

கலைந்த இரைச்சலிலிருந்து திடமான வண்ணங்கள் வரை, விரிக்கப்பட்ட முகங்களாகவும் சிறிய கனசதுரங்களாகவும் காட்டப்படும், தீர்க்கப்படும் 256 அடுக்குக் கனசதுரம் ஒன்றின் எட்டுச் சட்டகங்கள்.

ஒவ்வொரு பக்கத்திலும் 256 அடுக்குகள் கொண்ட ஒரு கனசதுரத்தின் தீர்விலிருந்து, சம இடைவெளியிலான எட்டுச் சட்டகங்கள்: கலைக்கப்பட்ட முகங்கள் திடமான வண்ணங்களாக மாறுகின்றன. — படம் 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.

வழிமுறை, துண்டுகளின் எண்ணிக்கைக்கு நேர்விகிதமான நேரத்தில் இயங்குகிறது; ஆசிரியர்கள் திறந்த மூலத் தீர்வி ஒன்றை, அது சார்ந்திருக்கும் ஒவ்வொரு வலைப்பின்னலையும் முழுமையாகச் சரிபார்க்கும் நிரல்களுடன் (scripts) வழங்குகின்றனர். அவர்களின் சொந்த ஒப்பீட்டில், ஏறக்குறைய n = 840-இலிருந்து அது தற்போதுள்ள தீர்விகளை விட முன்னிலையில் உள்ளது; ஒவ்வொரு பக்கத்திலும் 256, 65,536 அடுக்குகள் கொண்ட கனசதுரங்களின் தீர்வுகளை அவர்கள் காட்சிப்படுத்தியுள்ளனர்.

2.37 என்பது ஓர் அணுகுநிலைக் (asymptotic) கூற்று: சூத்திரத்தின் சிறிய உறுப்புகள் துல்லியமாக நிர்ணயிக்கப்படவில்லை; எனவே குறிப்பிட்ட ஒரு கனசதுரத்துக்கு அது துல்லியமான எண்ணிக்கையைத் தருவதில்லை. எதிர்கால ஆதாயங்கள், துண்டுகளை வரிசைப்படுத்தும் வலைப்பின்னல்களாகக் குழுவாக்கும் பிற வழிகளிலிருந்தும், சிறந்த மூன்று-துண்டு இடமாற்றங்களிலிருந்தும் வரக்கூடும் என்று ஆசிரியர்கள் கூறுகின்றனர் — அதே இயந்திர அமைப்பு பிற மாபெரும் புதிர்களையும், நான்கு மற்றும் ஐந்து பரிமாண மீக்கனசதுரங்களையும் (hypercubes) கையாளக்கூடும்.