Pseudo-polynomial time
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, આંકડાકીય અલ્ગોરિધમ સ્યુડો-બહુપદી સમયમાં ચાલે છે જો તેનો ચાલી રહેલો સમય ઇનપુટના આંકડાકીય મૂલ્યમાં બહુપદી હોય (ઇનપુટમાં હાજર સૌથી મોટો પૂર્ણાંક)-પરંતુ ઇનપુટની લંબાઈમાં જરૂરી નથી (તેને રજૂ કરવા માટે જરૂરી બિટ્સની સંખ્યા), જે બહુપદી સમય અલ્ગોરિધમ્સ માટે કેસ છે. સામાન્ય રીતે, ઇનપુટનું આંકડાકીય મૂલ્ય ઇનપુટ લંબાઈમાં ઘાતાંકીય હોય છે, તેથી જ સ્યુડો-બહુપદી સમય અલ્ગોરિધમ આવશ્યકપણે ઇનપુટ લંબાઈના સંદર્ભમાં બહુપદી સમયમાં ચાલતું નથી. જાણીતા સ્યુડો-પોલિનોમિયલ ટાઇમ અલ્ગોરિધમ્સ સાથેની એન. પી.-પૂર્ણ સમસ્યાને વીકલી એન. પી.-પૂર્ણ કહેવામાં આવે છે. એન. પી.-પૂર્ણ સમસ્યાને મજબૂત એન. પી.-પૂર્ણ કહેવામાં આવે છે જો તે સાબિત થાય કે તે સ્યુડો-બહુપદી સમય અલ્ગોરિધમ દ્વારા ઉકેલી શકાતી નથી સિવાય કે. એન. પી.-કઠોરતાના મજબૂત/નબળા પ્રકારોને સમાન રીતે વ્યાખ્યાયિત કરવામાં આવે છે. ઉદાહરણો પ્રાથમિક પરીક્ષણ સંખ્યા n અવિભાજ્ય છે કે કેમ તે ચકાસવાની સમસ્યાનો વિચાર કરો, નિષ્કપટ રીતે તપાસ કરીને કે કોઈ સંખ્યા સમાનરૂપે વિભાજિત થતી નથી કે કેમ. આ અભિગમ વિભાગો સુધી લઇ શકે છે, જે n ની કિંમતમાં પેટા-રેખીય છે પરંતુ n ની લંબાઈમાં ઘાતાંકીય છે (જે લગભગ છે). ઉદાહરણ તરીકે, n ની લંબાઈ માત્ર 11 અંકો હોવા છતાં, n કરતા થોડી ઓછી સંખ્યાને આશરે 100,000 વિભાગોની જરૂર પડશે. વધુમાં કોઈ પણ વ્યક્તિ સરળતાથી ઇનપુટ (જેમ કે, 300-અંકની સંખ્યા) લખી શકે છે, જેના માટે આ અલ્ગોરિધમ અવ્યવહારુ છે. કોમ્પ્યુટેશનલ જટિલતા (એન્કોડેડ) ઇનપુટની લંબાઈના સંદર્ભમાં મુશ્કેલીને માપે છે, તેથી આ નિષ્કપટ અલ્ગોરિધમ ખરેખર ઘાતાંકીય છે. જોકે, તે સ્યુડો-બહુપદી સમય છે. આ અલ્ગોરિધમનો સાચો બહુપદી આંકડાકીય અલ્ગોરિધમ સાથે વિરોધાભાસ કરો-કહો કે, ઉમેરા માટેનો સીધો અલ્ગોરિધમઃ બે 9-અંકની સંખ્યાઓ ઉમેરવામાં લગભગ 9 સરળ પગલાં લાગે છે, અને સામાન્ય રીતે અલ્ગોરિધમ ખરેખર ઇનપુટની લંબાઈમાં રેખીય હોય છે. ઉમેરવામાં આવતી વાસ્તવિક સંખ્યાઓ (અબજોમાં) ની સરખામણીમાં, અલ્ગોરિધમને "સ્યુડો-લઘુગણક સમય" કહી શકાય, જોકે આ પ્રકારનો શબ્દ પ્રમાણભૂત નથી. આમ, 300 અંકની સંખ્યાઓ ઉમેરવી અવ્યવહારુ નથી. તેવી જ રીતે, લાંબો વિભાજન એ વર્ગાત્મક છેઃ m-અંકની સંખ્યાને n-અંકની સંખ્યા દ્વારા પગલાંઓમાં વિભાજિત કરી શકાય છે (બિગ O નોટેશન જુઓ.) પ્રાથમિકતાના કિસ્સામાં, તે તારણ આપે છે કે n એ અવિભાજ્ય (2002 માં શોધાયેલ) છે કે કેમ તે ચકાસવા માટે એક અલગ અલ્ગોરિધમ છે જે સમયસર ચાલે છે. નાપસેક સમસ્યા નાપસેકની સમસ્યામાં, આપણને નાપસેકની મહત્તમ વજન ક્ષમતા સાથે વજન અને મૂલ્યવાળી વસ્તુઓ આપવામાં આવે છે. ધ્યેય નીચેની ઓપ્ટિમાઇઝેશન સમસ્યાને હલ કરવાનો છે; અનૌપચારિક રીતે, મહત્તમ મૂલ્ય મેળવવા માટે વસ્તુઓને નાપસંદમાં ફિટ કરવાની શ્રેષ્ઠ રીત કઈ છે? અને વિષયને મહત્તમ કરો. આ સમસ્યાનું સમાધાન એન. પી.-હાર્ડ છે, તેથી બહુપદી સમય અલ્ગોરિધમ અશક્ય છે સિવાય કે. જો કે, ડાયનેમિક પ્રોગ્રામિંગનો ઉપયોગ કરીને ટાઇમ અલ્ગોરિધમ શક્ય છે; કારણ કે સંખ્યાને વર્ણવવા માટે માત્ર બિટ્સની જરૂર હોય છે, આ અલ્ગોરિધમ સ્યુડો-બહુપદી સમયમાં ચાલે છે. બિન-આંકડાકીય સમસ્યાઓ માટે સામાન્યીકરણ જોકે સ્યુડો-બહુપદી સમયની કલ્પનાનો ઉપયોગ લગભગ સંપૂર્ણપણે આંકડાકીય સમસ્યાઓ માટે થાય છે, આ ખ્યાલને સામાન્યીકૃત કરી શકાય છેઃ જો m (n) એ સમસ્યાના કદ n ના બહુપદી કાર્ય અને ઇનપુટના વધારાના ગુણધર્મ, k (n) કરતા વધારે ન હોય તો વિધેય m એ સ્યુડો-બહુપદી છે. (સંભવતઃ, k ને સમસ્યા સાથે સંબંધિત કંઈક તરીકે પસંદ કરવામાં આવે છે.) આ k ને ઇનપુટનું આંકડાકીય મૂલ્ય માનીને આંકડાકીય બહુપદી સમસ્યાઓને એક વિશેષ કેસ બનાવે છે. સંખ્યાના મૂલ્ય અને તેની લંબાઈ વચ્ચેનો તફાવત એન્કોડિંગમાંનો એક છેઃ જો આંકડાકીય ઇનપુટ્સ હંમેશા યુનરીમાં એન્કોડ કરવામાં આવે, તો સ્યુડો-બહુપદી બહુપદી સાથે એકરુપ થશે. મજબૂત રીતે એન. પી.-પૂર્ણ અર્ધ-બહુપદી સમયના અલ્ગોરિધમ્સના સંદર્ભો વિશ્લેષણ જટિલતા વર્ગો કોમ્પ્યુટેશનલ જટિલતા સિદ્ધાંત સ્યુડો-બહુપદી સમયના અલ્ગોરિધમ્સ પણ જુઓ.