NP-hardness
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, એન. પી.-કઠોરતા (બિન-નિર્ધારિત બહુપદી-સમયની કઠિનતા) એ સમસ્યાઓના વર્ગની વ્યાખ્યાયિત મિલકત છે જે અનૌપચારિક રીતે "ઓછામાં ઓછી એન. પી. માં સૌથી મુશ્કેલ સમસ્યાઓ જેટલી જ મુશ્કેલ હોય છે". એન. પી.-હાર્ડ સમસ્યાનું એક સરળ ઉદાહરણ સબસેટ સમ સમસ્યા છે. વધુ ચોક્કસ સ્પષ્ટીકરણ છેઃ એક સમસ્યા H એ NP-કઠણ છે જ્યારે NP માં દરેક સમસ્યા L ને બહુપદી સમયમાં H માં ઘટાડી શકાય છે; એટલે કે, H માટે ઉકેલ 1 એકમ સમય લે છે એમ ધારીને, Hs ઉકેલનો ઉપયોગ બહુપદી સમયમાં L ને ઉકેલવા માટે કરી શકાય છે. પરિણામે, કોઈપણ એન. પી.-હાર્ડ સમસ્યાને ઉકેલવા માટે બહુપદી સમય અલ્ગોરિધમ શોધવાથી એન. પી. માં તમામ સમસ્યાઓ માટે બહુપદી સમય અલ્ગોરિધમ મળશે. જેમ કે શંકા છે કે P ષ્ણ NP, તે અસંભવિત છે કે આવા અલ્ગોરિધમ અસ્તિત્વમાં છે. એવી શંકા છે કે એન. પી.-હાર્ડ સમસ્યાઓ માટે કોઈ બહુપદી-સમયના અલ્ગોરિધમ્સ નથી, પરંતુ તે સાબિત થયું નથી. વધુમાં, વર્ગ પી, જેમાં તમામ સમસ્યાઓ બહુપદી સમયમાં ઉકેલી શકાય છે, તે એન. પી. વર્ગમાં સમાયેલ છે. વ્યાખ્યા એક નિર્ણય સમસ્યા H એ NP-સખત હોય છે જ્યારે NP માં દરેક સમસ્યા L માટે, L થી H સુધી બહુપદી-સમયનો અનેક-એક ઘટાડો હોય છે. સમકક્ષ વ્યાખ્યા એ જરૂરી છે કે NP માં દરેક સમસ્યા L ને બહુપદી સમયમાં ઓરેકલ મશીન દ્વારા H માટે ઓરેકલ સાથે ઉકેલી શકાય છે. અનૌપચારિક રીતે, એક અલ્ગોરિધમનો વિચાર કરી શકાય છે જે આવા ઓરેકલ મશીનને H ને ઉકેલવા માટે સબરૂટિન તરીકે બોલાવે છે અને બહુપદી સમયમાં L ને ઉકેલે છે જો સબરૂટિન કોલ ગણતરી કરવા માટે માત્ર એક પગલું લે છે. બીજી વ્યાખ્યા એ છે કે એન. પી.-પૂર્ણ સમસ્યા જી થી એચ સુધી બહુપદી-સમયનો ઘટાડો હોવો જરૂરી છે. જેમ કે એન. પી. માં કોઈપણ સમસ્યા એલ બહુપદી સમયમાં જી સુધી ઘટાડે છે, એલ બહુપદી સમયમાં એચ તરફ વળે છે તેથી આ નવી વ્યાખ્યા અગાઉના એકને સૂચવે છે. તે વર્ગ એન. પી.-હાર્ડને નિર્ણય સમસ્યાઓ સુધી મર્યાદિત કરતું નથી, અને તેમાં શોધ સમસ્યાઓ અથવા ઓપ્ટિમાઇઝેશન સમસ્યાઓ પણ શામેલ છે. પરિણામ જો P ષ્ણુત NP હોય, તો પછી NP-સખત સમસ્યાઓ બહુપદી સમયમાં ઉકેલી શકાતી નથી. કેટલીક એન. પી.-હાર્ડ ઓપ્ટિમાઇઝેશન સમસ્યાઓ બહુપદી-સમય અંદાજિત અમુક સ્થિર અંદાજ ગુણોત્તર (ખાસ કરીને, એ. પી. એક્સ. માં) અથવા કોઈપણ અંદાજ ગુણોત્તર (પી. ટી. એ. એસ. અથવા એફ. પી. ટી. એ. એસ. માં) સુધી પણ હોઈ શકે છે. ઉદાહરણો તમામ એન. પી.-પૂર્ણ સમસ્યાઓ પણ એન. પી.-હાર્ડ છે (એન. પી.-પૂર્ણ સમસ્યાઓની સૂચિ જુઓ). ઉદાહરણ તરીકે, સામાન્ય રીતે ટ્રાવેલિંગ સેલ્સમેન પ્રોબ્લેમ તરીકે ઓળખાતા ભારિત આલેખના તમામ ગાંઠોમાંથી ઓછામાં ઓછા ખર્ચે ચક્રીય માર્ગ શોધવાની ઓપ્ટિમાઇઝેશન સમસ્યા એન. પી.-હાર્ડ છે. સબસેટ સમ પ્રોબ્લેમ એ બીજું એક ઉદાહરણ છેઃ પૂર્ણાંકોનો સમૂહ આપવામાં આવે તો, શું તેમાંથી કોઈપણ ખાલી ન હોય તેવો સબસેટ શૂન્ય સુધી ઉમેરે છે? તે નિર્ણયની સમસ્યા છે અને એન. પી.-પૂર્ણ હોવાનું બને છે. ત્યાં નિર્ણય સમસ્યાઓ છે જે એન. પી.-સખત છે પરંતુ એન. પી.-પૂર્ણ નથી જેમ કે અટકાવવાની સમસ્યા. તે સમસ્યા છે જે પૂછે છે કે "પ્રોગ્રામ અને તેના ઇનપુટને જોતાં, શું તે કાયમ ચાલશે?" તે હા/ના નો પ્રશ્ન છે અને તે નિર્ણયની સમસ્યા પણ છે. તે સાબિત કરવું સરળ છે કે અટકાવવાની સમસ્યા એન. પી.-હાર્ડ છે પરંતુ એન. પી.-પૂર્ણ નથી. ઉદાહરણ તરીકે, બુલિયન સંતોષકારક સમસ્યાને ટ્યુરિંગ મશીનના વર્ણનમાં રૂપાંતરિત કરીને અટકાવવાની સમસ્યામાં ઘટાડી શકાય છે જે તમામ સત્ય મૂલ્ય સોંપણીઓનો પ્રયાસ કરે છે અને જ્યારે તે સૂત્રને સંતોષે છે તે શોધે છે ત્યારે તે અટકી જાય છે અને અન્યથા તે અનંત લૂપમાં જાય છે. તે જોવું પણ સરળ છે કે અટકાવવાની સમસ્યા એન. પી. માં નથી કારણ કે એન. પી. માંની તમામ સમસ્યાઓ મર્યાદિત સંખ્યામાં કામગીરીમાં નિર્ણાયક છે, પરંતુ અટકાવવાની સમસ્યા, સામાન્ય રીતે, અનિશ્ચિત છે. એનપી-હાર્ડ સમસ્યાઓ પણ છે જે ન તો એનપી-પૂર્ણ છે અને ન તો અનિર્ણિત છે. દાખલા તરીકે, સાચા પરિમાણિત બુલિયન સૂત્રોની ભાષા બહુપદી અવકાશમાં નિર્ણાયક છે, પરંતુ બિન-નિર્ધારિત બહુપદી સમય (જ્યાં સુધી NP = PSPACE ન હોય) માં નહીં. એન. પી.-નામકરણ સંમેલન એન. પી.-સખત સમસ્યાઓ જટિલતા વર્ગ એન. પી. ના ઘટકો હોવાની જરૂર નથી. એન. પી. કોમ્પ્યુટેશનલ જટિલતામાં કેન્દ્રિય ભૂમિકા ભજવે છે, તેથી તેનો ઉપયોગ કેટલાક વર્ગોના આધાર તરીકે થાય છેઃ કોમ્પ્યુટેશનલ નિર્ણય સમસ્યાઓના એન. પી. વર્ગ, જેના માટે આપેલ કોઈપણ હા-ઉકેલને નિર્ધારિત ટ્યુરિંગ મશીન દ્વારા બહુપદી સમયમાં ઉકેલ તરીકે ચકાસી શકાય છે (અથવા બહુપદી સમયમાં બિન-નિર્ધારિત ટ્યુરિંગ મશીન દ્વારા ઉકેલી શકાય છે). એન. પી.-હાર્ડ વર્ગની સમસ્યાઓ જે ઓછામાં ઓછી એન. પી. ની સૌથી મુશ્કેલ સમસ્યાઓ જેટલી જ મુશ્કેલ હોય છે. જે સમસ્યાઓ એન. પી.-સખત હોય તે એન. પી. ના ઘટકો હોવા જરૂરી નથી; ખરેખર, તેઓ નિર્ણાયક પણ ન હોઈ શકે. નિર્ણય સમસ્યાઓનો એન. પી.-પૂર્ણ વર્ગ જેમાં એન. પી. માં સૌથી મુશ્કેલ સમસ્યાઓ છે. દરેક એન. પી.-પૂર્ણ સમસ્યા એન. પી. માં હોવી જોઈએ. એન. પી.-સરળ એન. પી. જેટલું જ સખત હોય છે, પરંતુ એન. પી. માં જરૂરી નથી. એન. પી.-સમકક્ષ નિર્ણય સમસ્યાઓ કે જે એન. પી.-હાર્ડ અને એન. પી.-સરળ બંને હોય છે, પરંતુ એન. પી. માં જરૂરી નથી. જો પી અને એન. પી. અલગ હોય, તો એન. પી. ના પ્રદેશમાં નિર્ણયની સમસ્યાઓ અસ્તિત્વમાં છે જે પી અને એન. પી.-પૂર્ણ સમસ્યાઓ વચ્ચે આવે છે. (જો પી અને એન. પી. એક જ વર્ગ હોય, તો એન. પી.-મધ્યવર્તી સમસ્યાઓ અસ્તિત્વમાં નથી કારણ કે આ કિસ્સામાં દરેક એન. પી.-પૂર્ણ સમસ્યા પી. માં આવશે, અને વ્યાખ્યા મુજબ, એન. પી. માં દરેક સમસ્યાને એન. પી.-પૂર્ણ સમસ્યામાં ઘટાડી શકાય છે.) એપ્લિકેશન ક્ષેત્રો એન. પી.-હાર્ડ સમસ્યાઓનો ઘણીવાર નિયમો આધારિત ભાષાઓ સાથે સામનો કરવામાં આવે છે, જેમાં નીચેનાનો સમાવેશ થાય છેઃ અંદાજિત કમ્પ્યુટિંગ રૂપરેખાંકન ક્રિપ્ટોગ્રાફી ડેટા માઇનિંગ નિર્ણય સમર્થન ફિલોજેનેટિક્સ આયોજન પ્રક્રિયા દેખરેખ અને નિયંત્રણ રોસ્ટર અથવા સમયપત્રક રૂટીંગ/વાહન રૂટીંગ સમયપત્રક પણ જુઓ વણઉકેલાયેલી સમસ્યાઓની સૂચિ ઘટાડો (જટિલતા) અજાણતા સંદર્ભો જટિલતા વર્ગો