Generalized distributive law
સામાન્યીકૃત વિતરણ કાયદો (જી. ડી. એલ.) એ વિતરણ ગુણધર્મનું સામાન્યીકરણ છે જે સામાન્ય સંદેશ પસાર કરવાના અલ્ગોરિધમને જન્મ આપે છે. તે માહિતી સિદ્ધાંત, ડિજિટલ સંચાર, સંકેત પ્રક્રિયા, આંકડાશાસ્ત્ર અને કૃત્રિમ બુદ્ધિ સમુદાયોમાં ઘણા લેખકોના કાર્યનું સંશ્લેષણ છે. શ્રીનિવાસ એમ. અજી અને રોબર્ટ જે. મેકલીસ દ્વારા સમાન શીર્ષક સાથે અર્ધ-ટ્યુટોરિયલમાં કાયદો અને અલ્ગોરિધમ રજૂ કરવામાં આવ્યા હતા. પરિચય "ગણિતમાં વિતરણ કાયદો એ ગુણાકાર અને સરવાળાની કામગીરીને લગતા કાયદા છે, જે પ્રતીકાત્મક રીતે વર્ણવવામાં આવે છે, એટલે કે, એકવિધ પરિબળનું વિતરણ કરવામાં આવે છે, અથવા અલગથી લાગુ કરવામાં આવે છે, દ્વિપદી પરિબળના દરેક પદ પર, જે ઉત્પાદનમાં પરિણમે છે"-બ્રિટાનિકા જેમ કે વ્યાખ્યા પરથી અવલોકન કરી શકાય છે, અંકગણિત અભિવ્યક્તિમાં વિતરણ કાયદાના ઉપયોગથી તેમાં કામગીરીની સંખ્યામાં ઘટાડો થાય છે. અગાઉના ઉદાહરણમાં કામગીરીની કુલ સંખ્યા ત્રણ (બે ગુણાકાર અને એક ઉમેરો) થી ઘટીને બે (એક ગુણાકાર અને એક ઉમેરો) થઈ ગઈ હતી. વિતરણ કાયદાનું સામાન્યીકરણ ઝડપી અલ્ગોરિધમ્સના મોટા પરિવાર તરફ દોરી જાય છે. આમાં એફ. એફ. ટી. અને વિટરબી અલ્ગોરિધમનો સમાવેશ થાય છે. આને નીચે આપેલા ઉદાહરણમાં વધુ ઔપચારિક રીતે સમજાવવામાં આવ્યું છેઃ ક્યાં અને વાસ્તવિક મૂલ્યના કાર્યો છે, અને (કહો) અહીં આપણે પરિણામ મેળવવા માટે સ્વતંત્ર ચલ (,, અને) ને "હાંસિયામાં ધકેલી રહ્યા છીએ". જ્યારે આપણે કોમ્પ્યુટેશનલ જટિલતાની ગણતરી કરી રહ્યા છીએ, ત્યારે આપણે જોઈ શકીએ છીએ કે દરેક જોડી માટે, ત્રિપુટીને કારણે એવા શબ્દો છે કે જે દરેક પગલામાં એક ઉમેરો અને એક ગુણાકાર સાથે મૂલ્યાંકનમાં ભાગ લેવાની જરૂર છે. તેથી, જરૂરી ગણતરીઓની કુલ સંખ્યા છે. તેથી ઉપરોક્ત કાર્યની એસિમ્પ્ટોટિક જટિલતા છે. જો આપણે સમીકરણના આર. એચ. એસ. પર વિતરણ નિયમ લાગુ કરીએ, તો આપણને નીચે મુજબ મળે છેઃ આ સૂચવે છે કે તેને ઉત્પાદન તરીકે વર્ણવી શકાય છે જ્યાં અને હવે, જ્યારે આપણે કોમ્પ્યુટેશનલ જટિલતાની ગણતરી કરી રહ્યા છીએ, ત્યારે આપણે જોઈ શકીએ છીએ કે જ્યારે આપણે મૂલ્યાંકન કરવા માટે ઉત્પાદનનો ઉપયોગ કરી રહ્યા હોઈએ ત્યારે તેમાં અને દરેકમાં ઉમેરાઓ થાય છે અને ગુણાકાર થાય છે. તેથી, જરૂરી ગણતરીઓની કુલ સંખ્યા છે. તેથી ગણતરીની એસિમ્પ્ટોટિક જટિલતા થી ઘટાડે છે. આ એક ઉદાહરણ દ્વારા દર્શાવે છે કે વિતરણ કાયદાને લાગુ કરવાથી કોમ્પ્યુટેશનલ જટિલતા ઘટે છે જે "ઝડપી અલ્ગોરિધમ" ની સારી લાક્ષણિકતાઓમાંની એક છે. ઇતિહાસ કેટલીક સમસ્યાઓ કે જે ઉકેલવા માટે વિતરણ કાયદાનો ઉપયોગ કરે છે તેને નીચે પ્રમાણે જૂથબદ્ધ કરી શકાય છે. ડીકોડિંગ અલ્ગોરિધમ્સ એ જી. ડી. એલ. જેવા અલ્ગોરિધમનો ઉપયોગ ગેલાજર દ્વારા લો ડેન્સિટી પેરિટી-ચેક કોડને ડીકોડ કરવા માટે કરવામાં આવ્યો હતો. ગેલાજરના કાર્યના આધારે ટેનરએ ટેનર ગ્રાફ રજૂ કર્યો અને ગેલાજર્સનું કાર્ય સંદેશ પસાર કરવાના સ્વરૂપમાં વ્યક્ત કર્યું. ટેનર્સના આલેખે વિટરબી અલ્ગોરિધમને સમજાવવામાં પણ મદદ કરી. ફોર્ની દ્વારા અવલોકન કરવામાં આવ્યું છે કે વિટરબીના કન્વોલ્યુશનલ કોડ્સના મહત્તમ સંભાવના ડીકોડિંગમાં પણ જી. ડી. એલ. જેવી સામાન્યતાના અલ્ગોરિધમનો ઉપયોગ કરવામાં આવ્યો હતો. 2. ફોરવર્ડ-બેકવર્ડ અલ્ગોરિધમ માર્કોવ સાંકળમાં સ્થિતિઓને ટ્રેક કરવા માટે એક અલ્ગોરિધમ તરીકે મદદ કરે છે. અને આનો ઉપયોગ સામાન્યતા 3 જેવા જી. ડી. એલ. ના અલ્ગોરિધમનો પણ કરવામાં આવ્યો હતો. આર્ટિફિશિયલ ઇન્ટેલિજન્સ એ. આઈ. માં ઘણી સમસ્યાઓ હલ કરવા માટે જંકશન વૃક્ષોની કલ્પનાનો ઉપયોગ કરવામાં આવ્યો છે. બાલ્ટી નાબૂદીની વિભાવનાએ પણ ઘણી વિભાવનાઓનો ઉપયોગ કર્યો હતો. એમ. પી. એફ. સમસ્યા એમ. પી. એફ. અથવા ઉત્પાદન કાર્યને હાંસિયામાં ધકેલવું એ એક સામાન્ય ગણતરીની સમસ્યા છે જેમાં ખાસ કિસ્સામાં ઘણી શાસ્ત્રીય સમસ્યાઓનો સમાવેશ થાય છે જેમ કે સ્વતંત્ર હેડામાર્ડ ટ્રાન્સફોર્મની ગણતરી, મેમરી-ઓછી ચેનલ પર રેખીય કોડની મહત્તમ સંભાવના ડીકોડિંગ અને મેટ્રિક્સ સાંકળ ગુણાકાર. જી. ડી. એલ. ની શક્તિ એ હકીકતમાં રહેલી છે કે તે એવી પરિસ્થિતિઓને લાગુ પડે છે જેમાં ઉમેરાઓ અને ગુણાકાર સામાન્યીકૃત થાય છે. આ વર્તણૂકને સમજાવવા માટે પરિવર્તનીય અર્ધવિરામ એક સારું માળખું છે. તે ઓપરેટરો "" અને "" સાથે સમૂહ પર વ્યાખ્યાયિત કરવામાં આવે છે જ્યાં અને એક પરિવર્તનીય મોનોઇડ્સ છે અને વિતરણ કાયદો ધરાવે છે. ચાલો ચલ એવા હોઈએ કે જ્યાં એક મર્યાદિત સમૂહ હોય અને. અહીં. જો અને, દો,,, અને ક્યાં દો. ધારો કે કાર્યને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે, જ્યાં પરિવર્તનીય અર્ધવિરામ છે. ઉપરાંત, સ્થાનિક ક્ષેત્રો અને સ્થાનિક કર્નલો તરીકે નામ આપવામાં આવે છે. હવે વૈશ્વિક કર્નલને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છેઃ એમ. પી. એફ. સમસ્યાની વ્યાખ્યાઃ એક અથવા વધુ સૂચકાંકો માટે, વૈશ્વિક કર્નલના-માર્જિનલાઇઝેશનના મૂલ્યોના કોષ્ટકની ગણતરી કરો, જે આ રીતે વ્યાખ્યાયિત કાર્ય છે. તે અવલોકન કરી શકે છે કે સ્પષ્ટ રીતે ઉદ્દેશ્ય કાર્યની ગણતરી માટે કામગીરીની જરૂર છે. આનું કારણ એ છે કે ઉદ્દેશ્ય કાર્યની ગણતરીમાં ઉમેરાઓ અને ગુણાકાર જરૂરી છે. GDL અલ્ગોરિધમ જે આગામી વિભાગમાં સમજાવવામાં આવ્યું છે તે આ કોમ્પ્યુટેશનલ જટિલતાને ઘટાડી શકે છે. નીચે એમ. પી. એફ. સમસ્યાનું ઉદાહરણ છે. ચાલો અને તે અને જેવા ચલ બનો. અહીં અને. આ ચલોનો ઉપયોગ કરીને આપેલા કાર્યો છે અને અને આપણે ગણતરી કરવાની અને વ્યાખ્યાયિત કરવાની જરૂર છેઃ અહીં સ્થાનિક ક્ષેત્રો અને સ્થાનિક કર્નલોને નીચે પ્રમાણે વ્યાખ્યાયિત કરવામાં આવે છેઃ ઉદ્દેશ્ય કાર્ય ક્યાં છે અને ઉદ્દેશ્ય કાર્ય ક્યાં છે. અન્ય એક ઉદાહરણનો વિચાર કરો કે જ્યાં અને તે વાસ્તવિક મૂલ્યવાન કાર્ય છે. હવે, આપણે એમ. પી. એફ. સમસ્યાને ધ્યાનમાં લઈશું જ્યાં પરિવર્તનીય અર્ધસૂત્રણને સામાન્ય ઉમેરા અને ગુણાકાર સાથે વાસ્તવિક સંખ્યાઓના સમૂહ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે અને સ્થાનિક ડોમેન્સ અને સ્થાનિક કર્નલોને નીચે પ્રમાણે વ્યાખ્યાયિત કરવામાં આવે છેઃ હવે વૈશ્વિક કર્નલને સ્થાનિક કર્નલોના ગુણાકાર તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, તે છે અને સ્થાનિક ડોમેન પર ઉદ્દેશ્ય કાર્ય છે. તેથી આપણે જોઈ શકીએ છીએ કે હેડમર્ડ ટ્રાન્સફોર્મની ગણતરી એ એમ. પી. એફ. સમસ્યાનો એક વિશેષ કેસ છે. વધુ ઉદાહરણો એ સાબિત કરવા માટે દર્શાવી શકાય છે કે એમ. પી. એફ. સમસ્યા ઉપર વર્ણવ્યા મુજબ ઘણી શાસ્ત્રીય સમસ્યાના વિશેષ કિસ્સાઓ બનાવે છે જેની વિગતો જી. ડી. એલ. માં મળી શકે છેઃ એમ. પી. એફ. સમસ્યાને ઉકેલવા માટેનું એક અલ્ગોરિધમ જો કોઈ આપેલ સમૂહના ઘટકો વચ્ચે સંબંધ શોધી શકે, તો પછી કોઈ વ્યક્તિ માન્યતા પ્રસારની કલ્પનાને આધારે એમ. પી. એફ. સમસ્યાનું સમાધાન કરી શકે છે જે "સંદેશ પસાર કરવાની" તકનીકનો વિશેષ ઉપયોગ છે. જરૂરી સંબંધ એ છે કે સ્થાનિક ડોમેન્સના આપેલ સમૂહને જંકશન ટ્રીમાં ગોઠવી શકાય છે. બીજા શબ્દોમાં કહીએ તો, આપણે વૃક્ષના શિરોબિંદુઓ જેવા ઘટકો સાથે ગ્રાફ સૈદ્ધાંતિક વૃક્ષ બનાવીએ છીએ, જેમ કે કોઈપણ બે મનસ્વી શિરોબિંદુઓ માટે કહો અને ક્યાં અને ત્યાં આ બે શિરોબિંદુઓ વચ્ચે એક ધાર અસ્તિત્વમાં છે, પછી અનુરૂપ લેબલનું આંતરછેદ, એટલે કે, દરેક શિરોબિંદુ પર લેબલનો સબસેટ છે જે અનન્ય માર્ગ પર છે. ઉદાહરણ તરીકે, ઉદાહરણ 1: નીચેના નવ સ્થાનિક ડોમેન્સને ધ્યાનમાં લોઃ ઉપર આપેલા સ્થાનિક ડોમેન્સના સમૂહ માટે, નીચે બતાવ્યા પ્રમાણે કોઈ તેમને જંકશન ટ્રીમાં ગોઠવી શકે છેઃ તેવી જ રીતે જો નીચેના જેવા અન્ય સમૂહને આપવામાં આવે તો ઉદાહરણ 2: નીચેના ચાર સ્થાનિક ડોમેન્સને ધ્યાનમાં લોઃ પછી ફક્ત આ સ્થાનિક ડોમેન્સ સાથે વૃક્ષનું નિર્માણ કરવું શક્ય નથી કારણ કે મૂલ્યોના આ સમૂહમાં કોઈ સામાન્ય ડોમેન્સ નથી જે ઉપરના સમૂહના કોઈપણ બે મૂલ્યો વચ્ચે મૂકી શકાય. જો કે, જો નીચે બતાવ્યા પ્રમાણે બે ડમી ડોમેન્સ ઉમેરવામાં આવે તો જંકશન ટ્રીમાં અપડેટેડ સેટને ગોઠવવાનું શક્ય અને સરળ પણ હશે. 5., 6. એ જ રીતે ડોમેન્સના આ સમૂહ માટે, જંકશન ટ્રી નીચે બતાવ્યા પ્રમાણે દેખાય છેઃ સામાન્યીકૃત વિતરણ કાયદો (GDL) અલ્ગોરિધમ ઇનપુટઃ સ્થાનિક ડોમેન્સનો સમૂહ. આઉટપુટઃ ડોમેન્સના આપેલ સમૂહ માટે, સમસ્યાનું સમાધાન કરવા માટે જરૂરી કામગીરીની સંભવિત લઘુતમ સંખ્યાની ગણતરી કરવામાં આવે છે. તેથી, જો અને જંકશન વૃક્ષની ધાર દ્વારા જોડાયેલા હોય, તો પછી થી નો સંદેશ એ કાર્ય દ્વારા આપવામાં આવેલ મૂલ્યોનો સમૂહ/કોષ્ટક છેઃ તમામ કાર્યોથી શરૂ કરવા માટે એટલે કે. આપેલ વૃક્ષમાં અને તેના તમામ સંયોજનો માટે, સમાન રીતે વ્યાખ્યાયિત કરવામાં આવે છે અને જ્યારે કોઈ ચોક્કસ સંદેશ અપડેટ કરવામાં આવે છે, ત્યારે તે નીચે આપેલા સમીકરણને અનુસરે છે. = જ્યાં તેનો અર્થ એ છે કે તે વૃક્ષની બાજુમાં આવેલું શિરોબિંદુ છે. એ જ રીતે દરેક શિરોબિંદુની એક સ્થિતિ હોય છે જેને કાર્યમાંથી મૂલ્યો ધરાવતા કોષ્ટક તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, જેમ કે સંદેશાઓ એક સરખા રીતે 1 થી કેવી રીતે પ્રારંભ કરે છે, તે સ્થિતિને સ્થાનિક કર્નલ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, પરંતુ જ્યારે પણ અપડેટ થાય છે, ત્યારે તે નીચેના સમીકરણને અનુસરે છેઃ અલ્ગોરિધમનો મૂળભૂત કાર્ય ઇનપુટ તરીકે સ્થાનિક ડોમેન્સના આપેલ સમૂહ માટે, આપણે શોધી કાઢીએ છીએ કે આપણે જંકશન ટ્રી બનાવી શકીએ કે કેમ, ક્યાં તો સેટનો સીધો ઉપયોગ કરીને અથવા પહેલા સેટમાં ડમી ડોમેન્સ ઉમેરીને અને પછી જંકશન ટ્રી બનાવીને, જો બાંધકામ જંકશન શક્ય ન હોય તો એલ્ગોરિધમ આઉટપુટ કે આપેલ સમીકરણ સમસ્યાની ગણતરી કરવા માટે પગલાંની સંખ્યાને ઘટાડવાનો કોઈ રસ્તો નથી, પરંતુ એકવાર આપણી પાસે જંકશન ટ્રી હોય, એલ્ગોરિધમને સંદેશાઓ સુનિશ્ચિત કરવા પડશે અને સ્થિતિઓની ગણતરી કરવી પડશે, આ કરીને આપણે જાણી શકીએ છીએ કે ક્યાં પગલાં છે સંદેશ પસાર કરવાનું સમયપત્રક અને સ્થિતિની ગણતરી આપણે અહીં બે વિશેષ કિસ્સાઓ વિશે વાત કરવા જઈ રહ્યા છીએ જેમ કે સિંગલ વર્ટેક્સ પ્રોબ્લેમ જેમાં ઉદ્દેશ્ય કાર્યની ગણતરી માત્ર એક જ શિરોબિંદુ પર કરવામાં આવે છે અને બીજો એક ઓલ વર્ટીસ પ્રોબ્લેમ છે જ્યાં ધ્યેય તમામ શિરોબિંદુઓ પર ઉદ્દેશ્ય કાર્યની ગણતરી કરવાનો છે. ચાલો સિંગલ-વર્ટેક્સ સમસ્યાથી શરૂઆત કરીએ, GDL દરેક ધારને લક્ષિત શિરોબિંદુ તરફ નિર્દેશિત કરીને શરૂ કરશે. અહીં સંદેશાઓ માત્ર લક્ષિત શિરોબિંદુ તરફની દિશામાં મોકલવામાં આવે છે. નોંધ લો કે બધા નિર્દેશિત સંદેશાઓ માત્ર એક જ વાર મોકલવામાં આવે છે. સંદેશો લીફ નોડ્સથી શરૂ થાય છે (જ્યાં ડિગ્રી 1 છે) લક્ષ્ય શિરોબિંદુ તરફ જાય છે. સંદેશ પાંદડામાંથી તેના માતાપિતા સુધી અને પછી ત્યાંથી તેમના માતાપિતા સુધી અને ત્યાં સુધી જાય છે જ્યાં સુધી તે લક્ષ્ય શિરોબિંદુ સુધી ન પહોંચે. લક્ષ્ય શિરોબિંદુ તેની સ્થિતિની ગણતરી ત્યારે જ કરશે જ્યારે તે તેના તમામ પડોશીઓ પાસેથી તમામ સંદેશાઓ પ્રાપ્ત કરશે. એકવાર આપણી પાસે સ્થિતિ થઈ જાય, આપણને જવાબ મળી ગયો છે અને તેથી અલ્ગોરિધમ સમાપ્ત થાય છે. ઉદાહરણ તરીકે, ચાલો ઉપર આપેલા સ્થાનિક ડોમેન્સના સમૂહમાંથી બાંધવામાં આવેલા જંકશન વૃક્ષને ધ્યાનમાં લઈએ. ઉદાહરણ 1 માંથી સમૂહ, હવે આ ડોમેન્સ માટેનું સમયપત્રક કોષ્ટક છે (જ્યાં લક્ષ્ય શિરોબિંદુ છે). આમ સિંગલ વર્ટેક્સ જી. ડી. એલ. માટેની જટિલતાને અંકગણિત કામગીરી તરીકે દર્શાવી શકાય છે જ્યાં (નોંધઃ ઉપરોક્ત સમીકરણ માટેનું સમજૂતી લેખમાં પછીથી સમજાવવામાં આવ્યું છે) નું લેબલ છે. ની ડિગ્રી છે (એટલે. v) ને અડીને આવેલા શિરોબિંદુઓની સંખ્યા. ઓલ-વર્ટીસ સમસ્યાને ઉકેલવા માટે, આપણે જી. ડી. એલ. ને ઘણી રીતે સુનિશ્ચિત કરી શકીએ છીએ, તેમાંના કેટલાક સમાંતર અમલીકરણ છે જ્યાં દરેક રાઉન્ડમાં, દરેક રાજ્યને અપડેટ કરવામાં આવે છે અને દરેક સંદેશની ગણતરી કરવામાં આવે છે અને તે જ સમયે પ્રસારિત થાય છે. આ પ્રકારના અમલીકરણમાં રાજ્યો અને સંદેશાઓ રાઉન્ડની સંખ્યા પછી સ્થિર થશે જે વૃક્ષના વ્યાસની મહત્તમ બરાબર છે. આ બિંદુએ શિરોબિંદુઓની તમામ સ્થિતિઓ ઇચ્છિત ઉદ્દેશ્ય કાર્યની બરાબર હશે. આ સમસ્યા માટે જી. ડી. એલ. ને સુનિશ્ચિત કરવાની બીજી રીત ક્રમિક અમલીકરણ છે જ્યાં તે સિંગલ વર્ટેક્સ સમસ્યા જેવી જ હોય છે સિવાય કે જ્યાં સુધી જરૂરી સમૂહના તમામ શિરોબિંદુઓને તેમના તમામ પડોશીઓ તરફથી તમામ સંદેશા ન મળે અને તેમની સ્થિતિની ગણતરી ન થાય ત્યાં સુધી આપણે અલ્ગોરિધમ બંધ કરતા નથી. આમ આ અમલીકરણ માટે જરૂરી અંકગણિતની સંખ્યા મોટાભાગે અંકગણિત કામગીરીઓ છે. જંકશન વૃક્ષનું નિર્માણ જંકશન વૃક્ષનું નિર્માણ કરવાની ચાવી સ્થાનિક ડોમેન ગ્રાફમાં છે, જે શિરોબિંદુઓ સાથે ભારિત સંપૂર્ણ ગ્રાફ છે. દરેક સ્થાનિક ક્ષેત્ર માટે એક, જેના દ્વારા નિર્ધારિત ધારનું વજન હોય છે. જો, તો આપણે કહીએ છીએ કે તેમાં સમાયેલ છે. દ્વારા સૂચવવામાં આવે છે (મહત્તમ વજનના વૃક્ષનું વજન), જે એન એ તે સમૂહમાં તત્વોની સંખ્યા છે તેના દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે. વધુ સ્પષ્ટતા અને વિગતો માટે, કૃપા કરીને આનો સંદર્ભ લો. સુનિશ્ચિત પ્રમેય ચાલો શિરોબિંદુ સમૂહ અને ધાર સમૂહ સાથેનું જંકશન વૃક્ષ હોઈએ. આ અલ્ગોરિધમમાં, સંદેશાઓ કોઈપણ ધાર પર બંને દિશામાં મોકલવામાં આવે છે, તેથી આપણે ધાર સમૂહ E ને શિરોબિંદુઓની ક્રમબદ્ધ જોડીના સમૂહ તરીકે કહી/ગણી શકીએ છીએ. ઉદાહરણ તરીકે, આકૃતિ 1 માંથી નીચે પ્રમાણે વ્યાખ્યાયિત કરી શકાય છે નોંધઃ ઉપર તમને તમામ સંભવિત દિશાઓ આપે છે કે જે સંદેશ વૃક્ષમાં મુસાફરી કરી શકે છે. જી. ડી. એલ. માટેના સમયપત્રકને તેના ઉપગણના મર્યાદિત ક્રમ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. જે સામાન્ય રીતે {} દ્વારા રજૂ થાય છે, અલ્ગોરિધમ ચલાવવાના રાઉન્ડ દરમિયાન અપડેટ કરેલા સંદેશાઓનો સમૂહ ક્યાં છે. કેટલાક સંકેતોને વ્યાખ્યાયિત/જોયા પછી, આપણે જોઈશું કે પ્રમેય કહે છે કે, જ્યારે આપણને એક સમયપત્રક આપવામાં આવે છે, ત્યારે અનુરૂપ સંદેશ લંબચોરસ વર્ટેક્સ સમૂહ સાથે મર્યાદિત નિર્દેશિત આલેખ તરીકે સૂચવવામાં આવે છે, જેમાં એક લાક્ષણિક તત્વ દ્વારા સૂચવવામાં આવે છે, પછી સંદેશ પસાર થયા પછી, શિરોબિંદુ પર સ્થિતિ એ વ્યાખ્યાયિત ઉદ્દેશ્ય હશે અને જો ત્યાં કોમ્પ્યુટેશનલ જટિલતા તરફનો માર્ગ છે. એટલે કે. આપણે સામાન્ય પદ્ધતિનો ઉપયોગ કરીને ગણતરી કરતી વખતે જરૂરી કામગીરીની સંખ્યા (અહીં સામાન્ય પદ્ધતિ દ્વારા અમારો અર્થ એવી પદ્ધતિઓ દ્વારા થાય છે કે જે સંક્ષિપ્ત પદ્ધતિઓમાં મેસેજ પાસિંગ અથવા જંકશન ટ્રીનો ઉપયોગ કરતી નથી જે GDL ની વિભાવનાઓનો ઉપયોગ કરતી નથી) અને સામાન્યીકૃત વિતરણ કાયદાનો ઉપયોગ કરીને કામગીરીની સંખ્યાની તુલના કરીએ છીએ. ઉદાહરણોઃ સૌથી સરળ કેસનો વિચાર કરો જ્યાં આપણે નીચેની અભિવ્યક્તિની ગણતરી કરવાની જરૂર છે. નિષ્કપટ રીતે આ અભિવ્યક્તિનું મૂલ્યાંકન કરવા માટે બે ગુણાકાર અને એક ઉમેરો જરૂરી છે. વિતરણ નિયમનો ઉપયોગ કરીને વ્યક્ત કરવામાં આવે ત્યારે અભિવ્યક્તિને સરળ ઓપ્ટિમાઇઝેશન તરીકે લખી શકાય છે જે કામગીરીની સંખ્યાને એક ઉમેરા અને એક ગુણાકારમાં ઘટાડે છે. ઉપરોક્ત સમજાવેલ ઉદાહરણની જેમ જ આપણે જી. ડી. એલ. લાગુ કરીને શક્ય તેટલી ઓછી કામગીરી કરવા માટે સમીકરણોને વિવિધ સ્વરૂપોમાં વ્યક્ત કરીશું. અગાઉના વિભાગોમાં સમજાવ્યા મુજબ આપણે જંકશન વૃક્ષોના ખ્યાલનો ઉપયોગ કરીને સમસ્યાનું સમાધાન કરીએ છીએ. આ વૃક્ષોના ઉપયોગ દ્વારા મેળવેલ ઓપ્ટિમાઇઝેશન વૃક્ષો પર અર્ધ જૂથની સમસ્યાને હલ કરીને મેળવેલ ઓપ્ટિમાઇઝેશન સાથે તુલનાત્મક છે. ઉદાહરણ તરીકે, સંખ્યાઓના ઓછામાં ઓછા જૂથને શોધવા માટે આપણે અવલોકન કરી શકીએ છીએ કે જો આપણી પાસે વૃક્ષ હોય અને બધા તત્વો વૃક્ષના તળિયે હોય, તો આપણે ઓછામાં ઓછી બે વસ્તુઓની સમાંતર તુલના કરી શકીએ છીએ અને પરિણામી લઘુત્તમ પિતૃને લખવામાં આવશે. જ્યારે આ પ્રક્રિયાનો વૃક્ષ ઉપર પ્રચાર કરવામાં આવશે ત્યારે તત્વોના જૂથના ઓછામાં ઓછા મૂળમાં જોવા મળશે. સંદેશ પસાર કરીને જંકશન વૃક્ષને ઉકેલવાની જટિલતા નીચે મુજબ છે આપણે અગાઉ વપરાયેલ સૂત્રને નીચેના સ્વરૂપમાં ફરીથી લખીએ છીએ. એ જ રીતે આપણે શિરોબિંદુ v ની સ્થિતિની ગણતરી કરવા માટે સમીકરણને નીચે પ્રમાણે ફરીથી લખીએ છીએ. ધારો કે આપણી પાસે ધાર છે તો આપણે સંદેશ સમીકરણનો ઉપયોગ કરીને સંદેશની ગણતરી કરીએ છીએ. ગણતરી કરવા માટે ઉમેરાઓ અને ગુણાકારની જરૂર પડે છે. (અમે તરીકે રજૂ કરીએ છીએ.) પરંતુ તેના માટે ઘણી શક્યતાઓ હશે. આમ સમગ્ર સંદેશમાં ઉમેરાઓ અને ગુણાકારની જરૂર પડશે વૃક્ષની કિનારીઓ તરફ સંદેશ મોકલવા માટે જરૂરી અંકગણિત કામગીરીની કુલ સંખ્યા ઉમેરાઓ અને ગુણાકારો હશે. એકવાર બધા સંદેશાઓ પ્રસારિત થઈ ગયા પછી અલ્ગોરિધમ સ્થિતિની ગણતરી સાથે સમાપ્ત થાય છે. આમ સ્થિતિની ગણતરી કરવા માટે જરૂરી ગણતરીઓની સંખ્યા નીચે ઉમેરાઓ અને ગુણાકાર તરીકે આપવામાં આવી છે આમ ગણતરીઓની સંખ્યાનો કુલ સરવાળો છે---- જ્યાં ધાર છે અને તેનું કદ દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે. જો આપણે ધારની જટિલતાને આ રીતે વ્યાખ્યાયિત કરીએ તો, તેને આ રીતે લખી શકાય છે આપણે હવે આકૃતિ 1 માં વ્યાખ્યાયિત સમસ્યા માટે ધારની જટિલતાની ગણતરી નીચે મુજબ કરીએ છીએ. (અહીં સીધી પદ્ધતિ દ્વારા અમારો અર્થ એવી પદ્ધતિઓ દ્વારા થાય છે જે સંદેશ પસાર કરવાનો ઉપયોગ કરતી નથી. સીધી પદ્ધતિનો ઉપયોગ કરીને લેવામાં આવેલો સમય દરેક નોડ પર સંદેશની ગણતરી કરવા અને દરેક નોડની સ્થિતિની ગણતરી કરવા માટેના સમયની સમકક્ષ હશે.) હવે આપણે ઓલ-વર્ટેક્સ સમસ્યાને ધ્યાનમાં લઈએ છીએ જ્યાં સંદેશ બંને દિશામાં મોકલવો પડશે અને બંને શિરોબિંદુઓ પર સ્થિતિની ગણતરી કરવી આવશ્યક છે. આમાં સમય લાગશે પરંતુ પૂર્વગણતરી દ્વારા આપણે ગુણાકારની સંખ્યાને ઘટાડી શકીએ છીએ. અહીં શિરોબિંદુની ડિગ્રી છે. ઉદાહરણ તરીકેઃ જો સંખ્યાઓ સાથેનો સમૂહ હોય. સ્પષ્ટને બદલે મહત્તમ ગુણાકાર સાથે તમામ ડી ઉત્પાદનોની ગણતરી કરવી શક્ય છે. આપણે જથ્થાનું પૂર્વગણતરી કરીને આ કરીએ છીએ અને આ ગુણાકાર લે છે. પછી જો આપણી પાસે છે તે સિવાય બધાનું ઉત્પાદન સૂચવે છે અને તેથી વધુને કુલ બનાવતા અન્ય ગુણાકારની જરૂર પડશે. જ્યારે જંકશન ટ્રીના નિર્માણની વાત આવે છે ત્યારે આપણે ઘણું બધું કરી શકતા નથી સિવાય કે આપણી પાસે ઘણા મહત્તમ વજનવાળા વૃક્ષ હોઈ શકે છે અને આપણે ઓછામાં ઓછા સાથે સ્પૅનિંગ ટ્રી પસંદ કરવું જોઈએ અને કેટલીકવાર આનો અર્થ જંકશન ટ્રીની જટિલતાને ઘટાડવા માટે સ્થાનિક ડોમેન ઉમેરવાનો હોઈ શકે છે. એવું લાગે છે કે જી. ડી. એલ. ત્યારે જ સાચું છે જ્યારે સ્થાનિક ડોમેન્સને જંકશન ટ્રી તરીકે વ્યક્ત કરી શકાય. પરંતુ એવા કિસ્સાઓમાં પણ જ્યાં ચક્ર અને સંખ્યાબંધ પુનરાવર્તનો હોય ત્યાં સંદેશાઓ લગભગ ઉદ્દેશ્ય કાર્ય સમાન હશે. લો ડેન્સિટી પેરિટી-ચેક કોડ્સ માટે ગેલાજર-ટેનર-વિબર્ગ અલ્ગોરિધમ પરના પ્રયોગો આ દાવાને ટેકો આપતા હતા. સંદર્ભ માહિતી સિદ્ધાંત અલ્ગોરિધમ્સ ગ્રાફિકલ મોડેલ્સ ડિજિટલ સિગ્નલ પ્રોસેસિંગ