NP-easy
જટિલતા સિદ્ધાંતમાં, જટિલતા વર્ગ એન. પી.-સરળતા એ કાર્ય સમસ્યાઓનો સમૂહ છે જે એન. પી. માં કેટલીક નિર્ણય સમસ્યા માટે ઓરેકલ સાથે નિર્ધારક ટ્યુરિંગ મશીન દ્વારા બહુપદી સમયમાં ઉકેલી શકાય છે. બીજા શબ્દોમાં કહીએ તો, સમસ્યા X એ NP-સરળ છે જો અને માત્ર ત્યારે જ જો NP માં કોઈ સમસ્યા Y અસ્તિત્વમાં હોય જેમ કે X બહુપદી-સમય ટ્યુરિંગ Y માટે ઘટાડી શકાય તેવું હોય. આનો અર્થ એ છે કે Y માટે ઓરેકલ આપવામાં આવે તો, એક અલ્ગોરિધમ અસ્તિત્વમાં છે જે બહુપદી સમયમાં X ને ઉકેલે છે (સંભવતઃ તે ઓરેકલનો વારંવાર ઉપયોગ કરીને). એન. પી.-ઇઝી એ એફ. પી. એન. પી. નું બીજું નામ છે (કાર્ય સમસ્યા લેખ જુઓ) અથવા એફ. ડી. 2. પી. માટે (બહુપદી પદાનુક્રમ લેખ જુઓ). એન. પી.-સરળ સમસ્યાનું ઉદાહરણ શબ્દમાળાઓની સૂચિને સૉર્ટ કરવાની સમસ્યા છે. નિર્ણયની સમસ્યા "સ્ટ્રિંગ A એ સ્ટ્રિંગ B કરતા મોટી છે" NP માં છે. ક્વિકસોર્ટ જેવા અલ્ગોરિધમ્સ છે જે તુલનાત્મક દિનચર્યામાં કોલની માત્ર બહુપદી સંખ્યાનો ઉપયોગ કરીને સૂચિને સૉર્ટ કરી શકે છે, ઉપરાંત વધારાના કામની બહુપદી રકમ. તેથી, સૉર્ટિંગ એન. પી.-સરળ છે. વધુ મુશ્કેલ સમસ્યાઓ પણ છે જે એન. પી.-સરળ છે. ઉદાહરણ માટે એન. પી.-સમકક્ષ જુઓ. એનપી-ઇઝીની વ્યાખ્યા ઘણા-એક ઘટાડાને બદલે ટ્યુરિંગ ઘટાડાનો ઉપયોગ કરે છે કારણ કે સમસ્યા વાયના જવાબો માત્ર સાચા અથવા ખોટા છે, પરંતુ સમસ્યા એક્સના જવાબો વધુ સામાન્ય હોઈ શકે છે. તેથી, સમાન જવાબ સાથે X ના ઉદાહરણને Y ના ઉદાહરણમાં અનુવાદિત કરવાની કોઈ સામાન્ય રીત નથી. નોંધો સંદર્ભો. જટિલતા વર્ગો