Cobham's thesis
કોભમનો થીસીસ, જેને કોભમ-એડમંડ્સ થીસીસ (એલન કોભમ અને જેક એડમંડ્સના નામ પરથી નામ આપવામાં આવ્યું છે) તરીકે પણ ઓળખવામાં આવે છે, તે ભારપૂર્વક જણાવે છે કે કોમ્પ્યુટેશનલ સમસ્યાઓની ગણતરી કોઈ કોમ્પ્યુટેશનલ ઉપકરણ પર ત્યારે જ કરી શકાય છે જ્યારે તેની ગણતરી બહુપદી સમયમાં કરી શકાય; એટલે કે, જો તે જટિલતા વર્ગ પીમાં હોય. આધુનિક શબ્દોમાં કહીએ તો, તે જટિલતા વર્ગ પી સાથે વ્યવહાર કરી શકાય તેવી સમસ્યાઓને ઓળખે છે. ઔપચારિક રીતે, બહુપદી સમયમાં સમસ્યાનું સમાધાન કરી શકાય તેવું કહેવાનો અર્થ એ છે કે એક અલ્ગોરિધમ અસ્તિત્વમાં છે, જે ઇનપુટ તરીકે સમસ્યાના એન-બીટ ઉદાહરણને આપવામાં આવે તો, મોટા-ઓ નોટેશનનો ઉપયોગ કરીને O (nc) સમયમાં ઉકેલ લાવી શકે છે અને c એ અચળાંક સાથે જે સમસ્યા પર આધાર રાખે છે પરંતુ સમસ્યા પર નહીં. "કાર્યોની આંતરિક કોમ્પ્યુટેશનલ મુશ્કેલી" શીર્ષક ધરાવતું એલન કોભમનું 1965નું પેપર જટિલતા વર્ગ પીની વિભાવનાના પ્રારંભિક ઉલ્લેખમાંનું એક છે, જેમાં બહુપદી સમયમાં નિર્ણાયક સમસ્યાઓનો સમાવેશ થાય છે. કોભેમે સિદ્ધાંત આપ્યો હતો કે આ જટિલતા વર્ગ સંભવિત રીતે ગણતરી કરી શકાય તેવી સમસ્યાઓના સમૂહને વર્ણવવાનો સારો માર્ગ છે. જેક એડમંડ્સના 1965 ના પેપર "પાથ્સ, ટ્રીઝ એન્ડ ફ્લાવર્સ" ને પણ પી ને ટ્રેક્ટેબલ સમસ્યાઓ સાથે ઓળખવાનો શ્રેય આપવામાં આવે છે. મર્યાદાઓ જ્યારે કોભમનો થીસીસ કોમ્પ્યુટેશનલ જટિલતાના સિદ્ધાંતના વિકાસમાં એક મહત્વપૂર્ણ સીમાચિહ્નરૂપ છે, ત્યારે એલ્ગોરિધમ્સની વ્યવહારુ શક્યતા પર લાગુ થતી તેની મર્યાદાઓ છે. આ થીસીસ અનિવાર્યપણે જણાવે છે કે "પી" નો અર્થ "સરળ, ઝડપી અને વ્યવહારુ" થાય છે, જ્યારે "નોટ ઇન પી" નો અર્થ "સખત, ધીમું અને અવ્યવહારુ" થાય છે. પરંતુ આ હંમેશા સાચું નથી, કારણ કે થીસીસ કેટલાક મહત્વપૂર્ણ ચલોને દૂર કરે છે જે વ્યવહારમાં રનટાઇમને પ્રભાવિત કરે છેઃ તે સતત પરિબળો અને નીચલા ક્રમની શરતોને અવગણે છે. તે ઘાતાંકના કદની અવગણના કરે છે. સમય પદાનુક્રમ પ્રમેય P માં સમસ્યાઓના અસ્તિત્વને સાબિત કરે છે જેમાં મનસ્વી રીતે મોટા ઘાતાંકોની જરૂર પડે છે. તે ઇનપુટના લાક્ષણિક કદની અવગણના કરે છે. ત્રણેય સંબંધિત છે અને અલ્ગોરિધમ્સના વિશ્લેષણ વિશેની સામાન્ય ફરિયાદો છે, પરંતુ તે ખાસ કરીને કોભમના થીસીસ પર લાગુ થાય છે, કારણ કે તે કાર્યદક્ષતા વિશે સ્પષ્ટ દાવો કરે છે. કોભમના થીસીસ હેઠળ, એક સમસ્યા કે જેના માટે શ્રેષ્ઠ અલ્ગોરિધમ n200 સૂચનાઓ લે છે તે શક્ય માનવામાં આવે છે, અને એક અલ્ગોરિધમ સાથેની સમસ્યા જે 20.00001 n સૂચનાઓ લે છે તે અવ્યવહારુ છે-ભલે કોઈ પહેલાના અલ્ગોરિધમ સાથે કદ n = 2 ના ઉદાહરણને ક્યારેય હલ કરી શક્યું ન હોય, જ્યારે કદ n = 106 ની પછીની સમસ્યાનું ઉદાહરણ મુશ્કેલી વિના ઉકેલી શકાય છે. એવા ક્ષેત્રોમાં જ્યાં વ્યવહારુ સમસ્યાઓમાં લાખો ચલ હોય છે (જેમ કે કામગીરી સંશોધન અથવા ઇલેક્ટ્રોનિક ડિઝાઇન ઓટોમેશન), ત્યાં O (n3) અલ્ગોરિધમ્સ પણ ઘણીવાર અવ્યવહારુ હોય છે. એક અલગ વિચારણા એ છે કે ઘણા કિસ્સાઓમાં, જો કોઈ ચોક્કસ ઉકેલ ન મળી શકે તો ઘણીવાર અંદાજિત ઉકેલો સાથે સંતુષ્ટ રહે છે. ઉદાહરણ તરીકે, ટ્રાવેલિંગ સેલ્સમેનની સમસ્યા બહુપદી સમયમાં બરાબર ઉકેલી શકાતી નથી તેવી વ્યાપક શંકા છે (તે એન. પી.-હાર્ડ છે), પરંતુ ક્રિસ્ટોફાઇડ્સ અલ્ગોરિધમ જેવી પદ્ધતિઓ સાથે બહુપદી સમયમાં સારા ઉકેલો મેળવી શકાય છે. સંદર્ભો કોમ્પ્યુટેશનલ જટિલતા સિદ્ધાંત