P-NP સમસ્યા એ ગણિતની સૌથી પડકારજનક સમસ્યાઓ પૈકીની એક છે, જે પૂછવામાં આવે છે કે આપેલ સમસ્યાનો સાચો જવાબ શોધવાની ઝડપી રીત છે કે કેમ. જો હલ કરવામાં આવે તો, તે એરક્રાફ્ટ શેડ્યુલિંગ અને સેમિકન્ડક્ટર ડિઝાઇન જેવા વૈવિધ્યસભર ઉદ્યોગોમાં ઑપ્ટિમાઇઝેશન સમસ્યાઓ હલ કરવાની રીતમાં ક્રાંતિ લાવી શકે છે.

એક ચોર દાગીનાની દુકાનમાં પ્રવેશ કરે છે, આસપાસ જુએ છે અને થોડીવાર માટે વિચાર કરે છે. “મને તમામ દાગીના લેવાનું ગમશે, પરંતુ કમનસીબે, મારી બેગનું વજન કેટલું હોઈ શકે તેની મર્યાદા છે. સૌથી વધુ પૈસા મેળવવા માટે મારે બેગમાં કયા રત્નો ભરવા જોઈએ?" તેમની કિંમતની ગણતરી કરવા માટે બેગમાં રત્નોના ઘણા બધા સંભવિત સંયોજનો છે. જો હાથથી ગણતરી કરવામાં ઘણો સમય લાગે, તો તમે શ્રેષ્ઠ અલ્ગોરિધમ્સ સાથે સૌથી અદ્યતન કમ્પ્યુટર્સ અને સોફ્ટવેરનો ઉપયોગ કરવા વિશે વિચારી શકો છો. કમનસીબે, આ સમસ્યાને ઝડપથી ઉકેલવા માટે હાલમાં કોઈ અલ્ગોરિધમ અસ્તિત્વમાં નથી. સૌથી શક્તિશાળી કમ્પ્યુટર્સ સાથે પણ, તે હજારો વર્ષ કે તેથી વધુ સમય લેશે. "નેપસેક પ્રોબ્લેમ" તરીકે ઓળખાતી આ સમસ્યાનું કારણ એટલું મુશ્કેલ છે કે તે P-NP સમસ્યા જેવી જ છે, એક ગણિતનો પડકાર જે માત્ર 53% ગણિતશાસ્ત્રીઓ માને છે કે 2100 પહેલા ઉકેલાઈ જશે.
P-NP સમસ્યા એ વિશ્વના ટોચના સાત ગણિત પડકારોમાંથી એક છે. યુ.એસ.માં ક્લે મેથેમેટિક્સ ઇન્સ્ટિટ્યૂટે 21મી સદી માટે સાત વણઉકેલાયેલી ગણિત સમસ્યાઓની યાદી આપી છે અને દરેક માટે $1 મિલિયનનું ઇનામ ઓફર કર્યું છે. માત્ર પોઈનકેરે અનુમાન જ સાબિત થયું છે, પરંતુ અન્ય છ, જેમાં P-NP સમસ્યાનો પણ સમાવેશ થાય છે, ઘણા ગણિતશાસ્ત્રીઓ દ્વારા વણઉકેલાયેલ અને પડકારવામાં આવેલ છે. સમાજના વિવિધ ક્ષેત્રોમાં ઓપ્ટિમાઈઝેશનની ઘણી સમસ્યાઓ, જેમાં ચોરના ઉદાહરણનો સમાવેશ થાય છે, ઉચ્ચ કોમ્પ્યુટેશનલ જટિલતા સાથે "સખત સમસ્યાઓ" છે. P-NP સમસ્યા એ સાબિત કરવાની છે કે શું આ "સખત સમસ્યાઓ" ઉકેલવા માટે કોઈ સરળ રસ્તો છે.

કોમ્પ્યુટેશનલ જટિલતા શું છે?

કોમ્પ્યુટેશનલ જટિલતા એ ઉદ્દેશ્ય માપદંડ છે કે આપણે જે સમસ્યાને હલ કરવાનો પ્રયાસ કરી રહ્યા છીએ તે કેટલી મુશ્કેલ છે. આ સંદર્ભમાં, કઠિનતાનો અર્થ એ નથી કે સમસ્યાનો કોઈ ઉકેલ નથી, પરંતુ ત્યાં કોઈ અલ્ગોરિધમ નથી કે જે સમસ્યાને ઝડપથી હલ કરી શકે.
અહીં એક સરળ ઉદાહરણ છે. ત્યાં 100 બોલ છે જેના પર વિવિધ રેન્ડમ નંબરો લખેલા છે.

– સમસ્યા 1: બોલ પર લખેલી સંખ્યાઓની મહત્તમ કિંમત કેટલી છે?
– સમસ્યા 2: શું ત્યાં બોલનો સમૂહ છે કે જે દડા પર લખેલી સંખ્યાઓનો સરવાળો 100 છે?

સમસ્યા 1 માટે, જો તમે એક બોલને બહાર કાઢો અને તેને બદલો જ્યારે તે તમારી પાસે હોય તેના કરતા મોટી સંખ્યા હોય, તો તમે જે નંબર સાથે સમાપ્ત કરો છો તે મહત્તમ છે, જેનો અર્થ છે કે તમારે કુલ 99 સરખામણી કરવાની જરૂર છે. તુલનાત્મક રીતે, સમસ્યા 2 માટે, આપણે 100 બોલ સાથે બનાવી શકાય તેવા દરેક સંયોજન માટે 100નો સરવાળો કરવાનો સમૂહ છે કે કેમ તે તપાસવાની જરૂર છે, જેનો અર્થ છે કે સૌથી ખરાબ કિસ્સામાં, આપણે લગભગ 2 થી 100મી ઘાત કરવાની જરૂર છે ( * ગણતરીના ઉપગણોની કુલ સંખ્યા). સુપર કોમ્પ્યુટર પ્રતિ સેકન્ડ એક ક્વાડ્રિલિયન ઓપરેશન કરે છે એમ ધારી લઈએ તો પણ, આમાં અકલ્પનીય લાંબો સમય લાગશે, લગભગ 23 ક્વાડ્રિલિયન વર્ષ.
એક અલ્ગોરિધમને બહુપદી સમય અલ્ગોરિધમ કહેવામાં આવે છે જો, જેમ જેમ બોલની સંખ્યા (N) વધે છે, તેમ તેમ ઓપરેશનની સંખ્યા (N-1) દડાની સંખ્યાના બહુપદી ફંક્શન કરતાં વધી જતી નથી, જેમ કે સમસ્યા 1 ના ઉકેલમાં. આવા અલ્ગોરિધમનું અસ્તિત્વ સરળ સમસ્યા અને મુશ્કેલ સમસ્યા વચ્ચેનો તફાવત હોઈ શકે છે.

P=NP?

નોંધ લો કે કઠિન સમસ્યા 2 નો જવાબ શોધવા માટે, જેના માટે કોઈ બહુપદી સમય અલ્ગોરિધમ અસ્તિત્વમાં નથી, તેને મોટી માત્રામાં ગણતરીની જરૂર છે, પરંતુ જવાબ સાચો છે તે ચકાસવું ખૂબ જ સરળ છે. બોલના સમૂહને જોતાં, લખેલ સંખ્યાઓનો સરવાળો 10 છે તે ચકાસવામાં 100 સેકન્ડથી ઓછો સમય લાગવો જોઈએ. બીજા શબ્દોમાં કહીએ તો, સમસ્યાની ગણતરી કરવી સરળ હોવાનો અર્થ એ નથી કે તેને હલ કરવાની કોઈ સરળ રીત છે. . શું તેને હલ કરવાનો કોઈ સરળ રસ્તો છે અને ગણિતશાસ્ત્રીઓને તે હજી સુધી મળ્યો નથી, અથવા તેને પ્રથમ સ્થાને હલ કરવાનો કોઈ સરળ રસ્તો નથી, તે જોવાનું બાકી છે. આ P-NP સમસ્યા છે.
P સેટ એ સરળ સમસ્યાઓનો સમૂહ છે જેનો જવાબ બહુપદીના સમયમાં આપી શકાય છે, જેમ કે સમસ્યા 1, અને NP સમૂહ એ સમસ્યાઓનો સમૂહ છે જે બહુપદીના સમયમાં શુદ્ધતા માટે ચકાસી શકાય છે. P-NP સમસ્યા એ સાબિત કરવાની સમસ્યા છે કે શું P-સેટ અને NP-સેટ સમકક્ષ સમૂહ છે. તે સ્વયં-સ્પષ્ટ છે કે પી-સેટ NP-સેટનો છે. જો કે, હજુ સુધી એ સાબિત થયું નથી કે NP સેટમાં દરેક સમસ્યા P સેટમાં છે. જો આ સાબિત થાય છે, તો તેનો અર્થ એ છે કે દરેક સમસ્યા કે જેની ગણતરી કરવી સરળ છે તેનો સરળ-થી-સંપૂર્ણ ઉકેલ છે, એટલે કે, અમને સમસ્યા 10 ઉકેલવા માટે હવે 28^2 વર્ષની જરૂર પડશે નહીં.

NP સમસ્યાઓ અને વાસ્તવિક જીવન

તે માત્ર P-NP સમસ્યાની ગાણિતિક મુશ્કેલી નથી જે તેને અત્યાર સુધીની ટોચની સાત ગણિત સમસ્યાઓમાંની એક બનાવે છે. તે સાબિત કરવા માટે ખૂબ જ મહત્વપૂર્ણ છે તેનું કારણ એ છે કે તે વાસ્તવિક-વિશ્વની સમસ્યાઓને ઉકેલવા સાથે નજીકથી સંબંધિત છે. એરપ્લેન શેડ્યુલિંગ, સેમિકન્ડક્ટર ડિઝાઇન, ડ્રિલ મશીન પ્લેસમેન્ટ, જીનોમિક ડેટા એનાલિસિસ, એસ્ટ્રોનોમિકલ ટેલિસ્કોપ પ્લેસમેન્ટ અને એક્સ-રે ક્રિસ્ટલોગ્રાફી જેવી વિવિધ ઉદ્યોગોમાં વાસ્તવિક-વિશ્વની સમસ્યાઓ એ NP-સખત સમસ્યાઓ છે જેને હલ કરવામાં લાંબો સમય લાગે છે. જો કે, અમે હજુ સુધી શ્રેષ્ઠ નિર્ણયો ઝડપથી લેવા માટે એક અલ્ગોરિધમ શોધી શક્યા નથી, અને અમને એ પણ ખબર નથી કે આવી અલ્ગોરિધમ અસ્તિત્વમાં છે કે કેમ. તેથી, બહુપદી-સમય અલ્ગોરિધમની ગેરહાજરીમાં, આપણે હાલમાં વાસ્તવિક-વિશ્વની સમસ્યાઓ વિશે કેવી રીતે નિર્ણય લઈ શકીએ?
ગણિત, કોમ્પ્યુટર સાયન્સ, ઔદ્યોગિક ઈજનેરી વગેરે જેવા વિવિધ ક્ષેત્રોના વિદ્વાનો વાસ્તવિક-દુનિયાની સમસ્યાઓને ઉકેલવા માટેના શ્રેષ્ઠ ઉકેલનો અંદાજ લગાવતા વિવિધ અંદાજિત ઉકેલોનું સંશોધન અને વિકાસ કરી રહ્યા છે. ચોરની સમસ્યાને ફરીથી ધ્યાનમાં લો: જો રત્નોના શ્રેષ્ઠ સંયોજનને શોધવામાં લાંબો સમય લાગશે, તો વિકલ્પ એ છે કે પ્રમાણમાં નાના નફા સાથે ઝડપથી અને અસરકારક રીતે નિર્ણય લેવાનો માર્ગ શોધવો. એક વિકલ્પ એ હોઈ શકે છે કે દરેક રત્નના વજન દીઠ મૂલ્યની ગણતરી કરો અને પહેલા વજન દીઠ સૌથી વધુ મૂલ્ય ધરાવતા રત્નોથી તમારી બેગ ભરો. આ એક અંદાજિત ઉકેલ છે જેને લોભી હ્યુરિસ્ટિક કહેવાય છે, જે નિર્ણયો ઝડપથી લેવાની જરૂર હોય ત્યારે વ્યવહારિક ઉપયોગ માટે મૂકવામાં આવે છે. જો કે આ અંદાજો શ્રેષ્ઠ નથી, તે સમયની મર્યાદાઓ સાથે વાસ્તવિક-વિશ્વની સમસ્યાઓમાં નિર્ણય લેવામાં ખૂબ મદદરૂપ થાય છે. વધુમાં, કેટલાક અંદાજિત ઉકેલો વધુ સુસંસ્કૃત બની રહ્યા છે, કેટલાક અંદાજો આપેલ સમસ્યા માટે 0.5% ભૂલની અંદર શ્રેષ્ઠ મૂલ્યનો અંદાજ કાઢવામાં સક્ષમ છે.

સુરક્ષા ઉદ્યોગ અને NP સમસ્યાઓ

ઉપરોક્ત ઉદ્યોગોથી વિપરીત, એક એવો ઉદ્યોગ છે જે NP સમસ્યાઓ ઉકેલવા માટે સરળ અલ્ગોરિધમ શોધવા માંગતો નથી. આ સુરક્ષા ઉદ્યોગ છે. વર્તમાન સુરક્ષા યોજનાઓ એવી રીતે ગોઠવવામાં આવી છે કે જે એનપી સમસ્યાનો વિપરીત ઉપયોગ કરે છે. જો તમે પાસવર્ડ જાણો છો, તો તે સાચો પાસવર્ડ છે તે ચકાસવું સરળ છે, પરંતુ તેને શોધવાનું સરળ નથી કારણ કે તેને શોધવા માટે કોઈ બહુપદી-સમય અલ્ગોરિધમ નથી. કદાચ સમગ્ર સુરક્ષા ઉદ્યોગ આશા રાખે છે કે P-NP સમસ્યા બારમાસી કોયડો રહેશે.
જો કે, P=NP સાબિત કરવાનો અર્થ એ નથી કે તમામ NP સમસ્યાઓ સરળતાથી ઉકેલી શકાય તેવી છે. જો કે, તે સ્પષ્ટ છે કે બહુપદી-સમય અલ્ગોરિધમનું અસ્તિત્વ ઘણા સંશોધકોને સખત NP સમસ્યાઓ માટે બહુપદી-સમય અલ્ગોરિધમનો અભ્યાસ કરવા માટે પ્રોત્સાહિત કરશે. આની કાર્યક્ષમતામાં સુધારણા અને વાસ્તવિક દુનિયાની સમસ્યાઓના ઑપ્ટિમાઇઝેશન પર નોંધપાત્ર અસર પડશે. તેનાથી વિપરિત, જો તે P≠NP બહાર આવે છે, તો તેનો અર્થ એ છે કે આવી કોઈ પદ્ધતિ નથી, જેનો અર્થ છે કે વાસ્તવિક દુનિયામાં ઘણી NP સમસ્યાઓ અવ્યવસ્થિત રહેશે. કોઈપણ રીતે, આ કોયડોનું પરિણામ શું આવશે તે જોવું રસપ્રદ રહેશે.