අද අප සාක්කුවේ දමාගෙන යන ස්මාර්ට් ජංගම දුරකථනය, මීට දශක කිහිපයකට පෙර මුළු කාමරයක්ම පුරා පැතිරී තිබූ දැවැන්ත පරිගණක යන්ත්‍රයකට වඩා දහස් ගුණයකින් බලවත්. තාක්ෂණයේ දියුණුවත් සමඟ පරිගණක කුඩා වීම අපට පුදුමයක් නොවේ. එහෙත්, පරිගණක විද්‍යාඥයින් දැන් අසන්නේ මෙයට හාත්පසින්ම වෙනස් පැනයකි: යම් කාර්යයක් නිම කිරීමට පරිගණකයකට සැබවින්ම අවශ්‍ය අවම මතක ඉඩ හෙවත් Memory ප්‍රමාණය කොපමණද?

මෙම පැනයට ලැබී ඇති නවතම පිළිතුර, පරිගණක විද්‍යාව පිළිබඳ අපගේ අවබෝධය උඩු යටිකුරු කිරීමට සමත් වී තිබේ.

වසර 50ක් පැරණි මතයක් බිඳ වැටෙයි

වසර 50කට ආසන්න කාලයක් පුරා, පරිගණක විද්‍යාඥයින් අතර එක් මූලික විශ්වාසයක් පැවතුණි. එනම්, පරිගණකයකට යම් කාර්යයක් කිරීමට ගතවන කාලය (එනම්, අවශ්‍ය පියවර ගණන) සහ ඒ සඳහා අවශ්‍ය මතක අවකාශය (memory space) අතර සෘජු සම්බන්ධයක් ඇති බවයි.

සරලව කිවහොත්, යම් ගණනය කිරීමකට පියවර 100ක් අවශ්‍ය නම්, එයට මතක ඒකක 100ක් පමණ අවශ්‍ය වේ යැයි සිතන ලදී. පියවර මිලියනයක කාර්යයකට, මතක ඒකක මිලියනයක් අවශ්‍ය වනු ඇත. මෙය, පොත් රාක්කයක් අකාරාදී පිළිවෙලට සකස් කිරීමේදී, සියලු පොත් එළියට ගෙන බිම තබා, නිවැරදි පිළිවෙලට නැවත ඇසිරීමට සමානය. එම ක්‍රමයට වැඩි ඉඩක් අවශ්‍ය වේ. අඩු ඉඩකින් එය කිරීමට නම් (රාක්කය මතම පොත් එකින් එක මාරු කරමින්), අධික කාලයක් ගතවේ. පරිගණක ක්‍රියා කරන්නේද මේ ආකාරයට යැයි මෙතෙක් කල් විශ්වාස කෙරිණි.

එහෙත්, මැසචුසෙට්ස් තාක්ෂණ ආයතනයේ (MIT) පරිගණක විද්‍යාඥයෙකු වන රයන් විලියම්ස්, මෙම පැරණි මතය සම්පූර්ණයෙන්ම බිඳ දමන සොයාගැනීමක් සිදු කර තිබේ. ඔහුගේ සොයාගැනීමට අනුව, ඕනෑම ගණනය කිරීමක් අප සිතුවාට වඩා බෙහෙවින් කුඩා මතක ඉඩක Memory ප්‍රමාණයක සිදු කළ හැකිය.

ඔහුගේ නව න්‍යායට අනුව, පියවර 100ක කාර්යයක් සඳහා අවශ්‍ය වන්නේ මතක ඒකක 10ක් ($\sqrt{100}$) පමණි. පියවර මිලියනයක කාර්යයක් සඳහා අවශ්‍ය වන්නේ මතක ඒකක 1000ක් ($\sqrt{1,000,000}$) පමණි! මෙය, පරිගණනයට අවශ්‍ය මතක අවකාශය පිළිබඳ අපගේ චින්තනයේ දැවැන්ත සම්පීඩනයකි.

මෙම සොයාගැනීම කෙතරම් අනපේක්ෂිතද යත්, විලියම්ස් පවා මුලදී පැවසුවේ, “මගේ සාධනයේ යම්කිසි වැරැද්දක් තිබිය යුතු යැයි මම සිතුවා, මොකද මෙය අතිශයින්ම බලාපොරොත්තු නොවූ දෙයක්,” යනුවෙනි.

මේ සියල්ල කළේ කෙසේද? ‘ගැටළු ලඝුකරණය’ නම් සංකල්පය

විලියම්ස්ගේ මෙම විප්ලවීය සාධනය පිටුපස ඇති රහස නම් “ගැටළු ලඝුකරණය” (Problem Reduction) නම් ප්‍රබල ගණිතමය සංකල්පයයි. මෙය තේරුම් ගැනීමට සරල උදාහරණයක් ගනිමු.

ඔබට සූට්කේසයක් ඇසිරීමේ ගැටළුවක් ඇතැයි සිතන්න. එය, මාසික අයවැයක් සැකසීමේ ගැටළුවට සමාන කළ හැක:

• සූට්කේසයේ ඉඩ ඔබේ මාසික අයවැය හා සමානයි.
• ඔබ අසුරන ඇඳුම්, ඔබේ මාසික වියදම් වලට සමානයි.
• සීමිත ඉඩකඩ තුළ ඇඳුම් දක්ෂ ලෙස ඇසිරීම, සීමිත මුදලකින් වියදම් කළමනාකරණය කිරීමට සමානයි.

මෙම ගැටළු දෙක පෙනුමෙන් වෙනස් වුවද, ගණිතමය වශයෙන් ඒවායේ ව්‍යුහය එක සමානය. එනම්, සීමිත සම්පතක් තුළ උපරිම ප්‍රයෝජන ගැනීමයි.

විලියම්ස් සිදු කළේද මෙවැනිම දෙයකි. ඔහු ඔප්පු කර පෙන්වූයේ, ඕනෑම සංකීර්ණ පරිගණකමය ගැටළුවක්, ඉතා කුඩා මතක ප්‍රමාණයක් දක්ෂ ලෙස නැවත නැවත භාවිත කරමින් විසඳිය හැකි සරල ගැටළුවක් බවට “පරිවර්තනය” කළ හැකි බවයි. එම සරල ගැටළුව ඉතා කුඩා මතක ප්‍රමාණයකින් විසඳිය හැකි බැවින්, මුල් සංකීර්ණ ගැටළුව ද එම කුඩා මතක ප්‍රමාණයෙන්ම විසඳිය හැකි විය යුතුය.

මෙහි ඇති වැදගත්කම කුමක්ද?

මිචිගන් විශ්වවිද්‍යාලයේ පරිගණක විද්‍යාඥයෙකු වන මහඩි චෙරග්චි පවසන්නේ, “මෙම දියුණුව ඇදහිය නොහැකියි. මීට පෙර, යම් කාලයකින් විසඳිය හැකි ගැටළු තිබුණත්, එතරම් කුඩා මතකයකින් ඒවා කළ නොහැකි යැයි බොහෝ දෙනා සිතුවා,” යනුවෙනි.

මෙම සොයාගැනීම අපට පෙන්වා දෙන්නේ, අනාගතයේදී පරිගණක තාක්ෂණයේ සැබෑ සීමාව වන්නේ අප සතුව ඇති මතක ප්‍රමාණය (RAM එක කොපමණ විශාලද යන්න) නොව, එම මතකය අප කෙතරම් බුද්ධිමත්ව සහ කාර්යක්ෂමව භාවිත කරන්නේද යන්න බවයි. පරිගණක දෘඩාංග (hardware) හැකිලීමේ යුගය අවසන් වෙමින්, දැන් අප පිවිසෙමින් සිටින්නේ එම දෘඩාංග වලින් උපරිම ප්‍රයෝජන ගන්නා බුද්ධිමත් මෘදුකාංග (software) සහ ඇල්ගොරිතම (algorithms) නිර්මාණය කිරීමේ නව යුගයකටයි.

Works cited

1. Reduction (complexity) – Wikipedia, https://en.wikipedia.org/wiki/Reduction_(complexity) 2. How to do a Reduction. (No, we’re not making sauce) | by Patience Shyu | Medium, https://medium.com/@patiences/how-to-do-a-reduction-648528183d26 3. Introduction to Analysis of Algorithms Reductions and NP-Completeness CS4820 Spring 2013 Monday, March 11, 2013, https://www.cs.cornell.edu/courses/cs4820/2013sp/Handouts/reductions.pdf 4. Mahdi Cheraghchi – Simons Institute, https://simons.berkeley.edu/people/mahdi-cheraghchi 5. Mahdi Cheraghchi | About | University of Michigan, https://experts.umich.edu/6292-mahdi-cheraghchi 6. Mahdi CHERAGHCHI | Associate Professor | PhD | University of Michigan, Ann Arbor | U-M | Department of Electrical Engineering and Computer Science (EECS) | Research profile – ResearchGate, https://www.researchgate.net/profile/Mahdi-Cheraghchi 7. Cheraghchi, Mahdi – Electrical Engineering and Computer Science – University of Michigan, https://eecs.engin.umich.edu/people/cheraghchi-mahdi/ 8. Home Page of Mahdi Cheraghchi, https://mahdi.ch/