NP-equivalent
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, જટિલતા વર્ગ એન. પી.-સમકક્ષ એ કાર્ય સમસ્યાઓનો સમૂહ છે જે એન. પી.-સરળ અને એન. પી.-હાર્ડ બંને છે. એન. પી.-સમકક્ષ એ કાર્ય સમસ્યાઓ માટે એન. પી.-પૂર્ણનું એનાલોગ છે. ઉદાહરણ તરીકે, FIND-SABSET-SAM સમસ્યા NP-સમકક્ષ છે. પૂર્ણાંકોના સમૂહને જોતાં, FIND-SUVSET-SUV એ પૂર્ણાંકોના કેટલાક બિન-ખાલી સબસેટ શોધવાની સમસ્યા છે જે શૂન્ય સુધી ઉમેરે છે (અથવા જો આવા કોઈ સબસેટ ન હોય તો ખાલી સેટ પરત કરે છે). આ ઓપ્ટિમાઇઝેશન સમસ્યા નિર્ણય સમસ્યા સબસેટ-સુમ જેવી જ છે. પૂર્ણાંકોના સમૂહને જોતાં, સબ્સેટ-સુમ એ શોધવાની સમસ્યા છે કે શું શૂન્યનો સરવાળો કરતો સબસેટ અસ્તિત્વમાં છે કે કેમ. એસ. યુ. બી. એસ. ઇ. ટી.-એસ. યુ. એમ. એન. પી. પૂર્ણ છે. FIND-SUVSET-SUV એ NP-સમકક્ષ છે તે બતાવવા માટે, આપણે બતાવવું જોઈએ કે તે NP-સખત અને NP-સરળ બંને છે. સ્પષ્ટપણે તે એન. પી.-હાર્ડ છે. જો આપણી પાસે એક બ્લેક બોક્સ હોત જેણે એકમ સમયમાં FIND-SABSET-SAM હલ કર્યું હોત, તો પછી SABSET-SAM ઉકેલવું સરળ હોત. ફક્ત બ્લેક બોક્સને એવા સબસેટ શોધવા માટે કહો કે જેનો સરવાળો શૂન્ય થાય, પછી તપાસો કે તે નોન એમ્પ્ટી સેટ પાછો આપે છે કે કેમ. તે એનપી-સરળ પણ છે. જો આપણી પાસે બ્લેક બોક્સ હોય જે યુનિટ સમયમાં સબસેટ-સુમને હલ કરે, તો આપણે તેનો ઉપયોગ ફાઈન્ડ-સબસેટ-સુમને ઉકેલવા માટે કરી શકીએ છીએ. જો તે ફોલ્સ રિટર્ન કરે છે, તો આપણે તરત જ ખાલી સેટ પરત કરીએ છીએ. નહિંતર, આપણે ક્રમમાં દરેક તત્વની મુલાકાત લઈએ છીએ અને તેને દૂર કરીએ છીએ, જો કે આપણે તેને દૂર કર્યા પછી પણ સબસેટ-સુમ સાચું પડશે. એકવાર આપણે દરેક તત્વની મુલાકાત લઈ લઈ લઈએ, પછી આપણે સાચોથી ખોટો જવાબ બદલ્યા વિના કોઈપણ તત્વને દૂર કરી શકીશું નહીં; આ સમયે મૂળ તત્વોના બાકીના સબસેટનો સરવાળો શૂન્ય હોવો જોઈએ. આ માટે આપણે એ નોંધવું જરૂરી છે કે તત્વોને પછીથી દૂર કરવાથી એ હકીકત બદલાતી નથી કે અગાઉના તત્વને દૂર કરવાથી જવાબ સાચોથી ખોટો થઈ ગયો. સ્યુડોકોડમાંઃ ફંક્શન FIND-SABSET-SAM (સમૂહ S) જો નહીં (SABSET-SAM (S)) S માં દરેક x માટે {} પરત કરે છે જો SABSET-SAM (S-{x}) S: = S-{x} વળતર S અન્ય જાણીતી NP-સમકક્ષ સમસ્યા મુસાફરી સેલ્સમેન સમસ્યા છે. સ્પષ્ટીકરણ આ સંદર્ભમાં એન. પી. નો અર્થ બિનનિર્ધારણીય બહુપદી સમય થાય છે. બુલિયન વિધેયોના એન. પી.-સમકક્ષતા વર્ગો પણ છે, જ્યાં એન. પી. નો અર્થ નિષેધ અને ક્રમચય છે. નોંધો સંદર્ભો. જટિલતા વર્ગો