P-complete
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, નિર્ણયની સમસ્યા પી-પૂર્ણ (કોમ્પ્લેક્સિટી ક્લાસ પી માટે પૂર્ણ) હોય છે જો તે પીમાં હોય અને પીમાં દરેક સમસ્યાને યોગ્ય ઘટાડો કરીને તેમાં ઘટાડી શકાય છે. પી-પૂર્ણ નિર્ણય સમસ્યાઓની કલ્પના આના વિશ્લેષણમાં ઉપયોગી છેઃ કઈ સમસ્યાઓને અસરકારક રીતે સમાંતર કરવી મુશ્કેલ છે, કઈ સમસ્યાઓને મર્યાદિત જગ્યામાં ઉકેલવી મુશ્કેલ છે. ખાસ કરીને જ્યારે પોલીટાઇમ-રિડ્યુસિબિલિટી કરતાં રિડ્યુસિબિલિટીની મજબૂત કલ્પનાઓને ધ્યાનમાં લેવામાં આવે છે. ઉપયોગમાં લેવાતા ઘટાડાનો ચોક્કસ પ્રકાર બદલાય છે અને તે સમસ્યાઓના ચોક્કસ સમૂહને અસર કરી શકે છે. સામાન્ય રીતે, બહુપદી-સમયના ઘટાડા કરતાં વધુ મજબૂત ઘટાડાનો ઉપયોગ કરવામાં આવે છે, કારણ કે બહુપદી-સમયના ઘટાડા હેઠળ પીની તમામ ભાષાઓ (ખાલી ભાષા અને તમામ શબ્દમાળાઓની ભાષા સિવાય) પી-પૂર્ણ હોય છે. જો આપણે NC ઘટાડાનો ઉપયોગ કરીએ, એટલે કે એવા ઘટાડા કે જે બહુપદી સંખ્યા સાથે સમાંતર કમ્પ્યુટર પર બહુપદી સમયમાં કામ કરી શકે છે, તો પછી બધી P-પૂર્ણ સમસ્યાઓ NC ની બહાર હોય છે અને તેથી બિનપુરવાર ધારણા હેઠળ અસરકારક રીતે સમાંતર કરી શકાતી નથી કે NC ષ્ણુપું. જો આપણે મજબૂત લોગ-સ્પેસ ઘટાડાનો ઉપયોગ કરીએ, તો આ સાચું રહે છે, પરંતુ વધુમાં આપણે શીખીએ છીએ કે તમામ P-પૂર્ણ સમસ્યાઓ L ની બહાર નબળી બિનપુરવાર ધારણા હેઠળ છે કે L ષ્ણુપું. આ પછીના કિસ્સામાં સમૂહ P-પૂર્ણ નાનો હોઈ શકે છે. પ્રેરણા વર્ગ પી, જેને સામાન્ય રીતે ક્રમિક કમ્પ્યુટર માટે તમામ "ટ્રેક્ટેબલ" સમસ્યાઓનો સમાવેશ કરવા માટે લેવામાં આવે છે, તેમાં વર્ગ એન. સી. નો સમાવેશ થાય છે, જેમાં તે સમસ્યાઓનો સમાવેશ થાય છે જેને સમાંતર કમ્પ્યુટર પર અસરકારક રીતે ઉકેલી શકાય છે. આનું કારણ એ છે કે સમાંતર કમ્પ્યુટર્સનું ક્રમિક મશીન પર અનુકરણ કરી શકાય છે. તે જાણીતું નથી કે NC = P. બીજા શબ્દોમાં કહીએ તો, તે જાણીતું નથી કે ત્યાં કોઈ ટ્રેક્ટેબલ સમસ્યાઓ છે કે જે સ્વાભાવિક રીતે ક્રમિક છે. જે રીતે વ્યાપકપણે શંકા કરવામાં આવે છે કે પી એ એન. પી. ની સમકક્ષ નથી, તેવી જ રીતે વ્યાપકપણે શંકા કરવામાં આવે છે કે એન. સી. એ પી. ની સમકક્ષ નથી. તેવી જ રીતે, વર્ગ એલ એ તમામ સમસ્યાઓ ધરાવે છે જે લઘુગણક અવકાશમાં ક્રમિક કમ્પ્યુટર દ્વારા ઉકેલી શકાય છે. આવા મશીનો બહુપદી સમયમાં ચાલે છે કારણ કે તેમાં બહુપદી સંખ્યાબંધ રૂપરેખાંકનો હોઈ શકે છે. એવી શંકા છે કે L ષ્ણ p; એટલે કે, બહુપદી સમયમાં ઉકેલી શકાય તેવી કેટલીક સમસ્યાઓને પણ લઘુગણકીય જગ્યા કરતાં વધુની જરૂર પડે છે. તેવી જ રીતે પી = એન. પી. પ્રશ્નનું વિશ્લેષણ કરવા માટે એન. પી.-પૂર્ણ સમસ્યાઓના ઉપયોગની જેમ, પી-પૂર્ણ સમસ્યાઓ, જેને "કદાચ સમાંતર નથી" અથવા "કદાચ સ્વાભાવિક રીતે ક્રમિક" સમસ્યાઓ તરીકે જોવામાં આવે છે, તે એન. સી. = પી. પ્રશ્નનો અભ્યાસ કરવા માટે સમાન રીતે કામ કરે છે. કેટલીક પી-પૂર્ણ સમસ્યાના ઉકેલને સમાંતર બનાવવાની કાર્યક્ષમ રીત શોધવી એ બતાવશે કે NC = P. તેને "સુપરલોગેરિધમિક જગ્યાની જરૂર હોય તેવી સમસ્યાઓ" તરીકે પણ વિચારી શકાય છે; પી-પૂર્ણ સમસ્યાનો લોગ-સ્પેસ ઉકેલ (લોગ-સ્પેસ ઘટાડા પર આધારિત વ્યાખ્યાનો ઉપયોગ કરીને) L = P સૂચવે છે. આ પાછળનો તર્ક એ તર્ક સાથે સમાન છે કે એન. પી.-પૂર્ણ સમસ્યાનો બહુપદી-સમય ઉકેલ P = NP સાબિત કરશેઃ જો આપણી પાસે P માં કોઈ સમસ્યાથી સમસ્યા A માં NC ઘટાડો હોય, અને A માટે NC ઉકેલ હોય, તો NC = P. તેવી જ રીતે, જો આપણી પાસે P માં કોઈ સમસ્યાથી સમસ્યા A માં લોગ-સ્પેસ ઘટાડો હોય, અને લોગ-સ્પેસ ઉકેલ હોય. P માં કોઈપણ x માટે, ટ્યુરિંગ મશીનનું એન્કોડિંગ આઉટપુટ કરો જે તેને બહુપદી-સમયમાં સ્વીકારે છે, x પોતે એન્કોડિંગ કરે છે, અને p ને અનુરૂપ સંખ્યાબંધ પગલાંઓ કે જે ટ્યુરિંગ મશીનની કામગીરી પર બહુપદી-સમય બંધાયેલ છે. જો અને માત્ર જો x એ L માં હોય તો મશીન M પગલાંઓમાં x પર અટકી જાય છે. સ્પષ્ટ રીતે, જો આપણે ક્રમિક કમ્પ્યુટરના સામાન્ય અનુકરણને સમાંતર કરી શકીએ (એટલે કે. ટ્યુરિંગ મશીનનું ટ્યુરિંગ મશીન સિમ્યુલેશન), પછી આપણે તે કમ્પ્યુટર પર ચાલતા કોઈપણ પ્રોગ્રામને સમાંતર બનાવી શકીશું. જો આ સમસ્યા NC માં હોય, તો પછી P માં દરેક અન્ય સમસ્યા પણ છે. જો પગલાંઓની સંખ્યા દ્વિસંગીમાં લખવામાં આવે, તો સમસ્યા EXPTIME-પૂર્ણ છે. આ સમસ્યા પી-પૂર્ણતાના સિદ્ધાંતમાં એક સામાન્ય યુક્તિ દર્શાવે છે. સમાંતર મશીન પર સમસ્યાનું ઝડપથી સમાધાન થઈ શકે છે કે કેમ તેમાં આપણને ખરેખર રસ નથી. આપણે ફક્ત તેમાં જ રસ ધરાવીએ છીએ કે શું સમાંતર મશીન તેને ક્રમિક મશીન કરતાં વધુ ઝડપથી હલ કરે છે. તેથી, આપણે સમસ્યાને ફરીથી લખવી પડશે જેથી ક્રમિક સંસ્કરણ પી માં હોય. તેથી જ આ સમસ્યાને યુનરીમાં લખવા માટે ટી જરૂરી છે. જો સંખ્યા T ને દ્વિસંગી સંખ્યા તરીકે લખવામાં આવે (n અને શૂન્યની સ્ટ્રિંગ, જ્યાં n = log T), તો સ્પષ્ટ ક્રમિક અલ્ગોરિધમનો સમય 2n લાગી શકે છે. બીજી બાજુ, જો T ને યુનરી સંખ્યા (n ની સ્ટ્રિંગ, જ્યાં n = T) તરીકે લખવામાં આવે, તો તે માત્ર સમય n લે છે. તે ક્રમિક સમસ્યાને પી માં મૂકે છે. પછી, જો તે સમાંતર હોય તો જ તે એન. સી. માં હશે. અન્ય ઘણી સમસ્યાઓ પી-પૂર્ણ સાબિત થઈ છે, અને તેથી વ્યાપકપણે સ્વાભાવિક રીતે ક્રમિક હોવાનું માનવામાં આવે છે. આમાં નીચેની સમસ્યાઓનો સમાવેશ થાય છે જે ઓછામાં ઓછા લોગસ્પેસ ઘટાડા હેઠળ પી-પૂર્ણ હોય છે, ક્યાં તો આપેલ છે, અથવા નિર્ણય-સમસ્યાના સ્વરૂપમાંઃ સર્કિટ વેલ્યુ પ્રોબ્લેમ (સીવીપી)-સર્કિટ, સર્કિટમાં ઇનપુટ્સ અને સર્કિટમાં એક ગેટ આપવામાં આવે છે, તે ગેટના આઉટપુટની ગણતરી કરો. સી. વી. પી. નો પ્રતિબંધિત કેસ-સી. વી. પી. ની જેમ, દરેક ગેટમાં બે ઇનપુટ્સ અને બે આઉટપુટ (એફ અને નોટ એફ) સિવાય, દરેક અન્ય સ્તર માત્ર એન્ડ ગેટ્સ છે, બાકીના ઓ. આર. ગેટ્સ છે (અથવા, સમાન રીતે, તમામ ગેટ્સ એન. એ. એન. ડી. ગેટ્સ છે, અથવા તમામ ગેટ્સ એન. ઓ. આર. ગેટ્સ છે), ગેટના ઇનપુટ્સ તરત જ અગાઉના સ્તરથી આવે છે રેખીય પ્રોગ્રામિંગ-રેખીય અસમાનતાના અવરોધોને આધિન રેખીય કાર્યને મહત્તમ બનાવો લેક્સિકોગ્રાફિકલી ફર્સ્ટ ડેપ્થ ફર્સ્ટ સર્ચ ઑર્ડરિંગ-નિશ્ચિત ક્રમાંકિત નિકટતા યાદીઓ સાથે ગ્રાફ આપવામાં આવે છે, અને નોડ્સ યુ અને વી, શું શિરોબિંદુ યુ એ નિકટતા સૂચિઓના ક્રમ દ્વારા પ્રેરિત ઊંડાઈ-પ્રથમ શોધમાં શિરોબિંદુ વી પહેલાં મુલાકાત લીધી છે? સંદર્ભ મુક્ત વ્યાકરણ સભ્યપદ-સંદર્ભ મુક્ત વ્યાકરણ અને શબ્દમાળાને જોતાં, શું તે શબ્દમાળાને તે વ્યાકરણ દ્વારા પેદા કરી શકાય છે? હોર્ન-સંતોષ-હોર્ન કલમોના સમૂહને જોતાં, શું કોઈ ચલ સોંપણી છે જે તેમને સંતુષ્ટ કરે છે? આ બૂલિયન સંતોષકારક સમસ્યાનું પી નું સંસ્કરણ છે. જીવનની રમત-કોનવેની જીવનની રમત, ચોક્કસ કોષ અને સમય ટી (યુનરીમાં) ની પ્રારંભિક રૂપરેખાંકનને જોતાં, શું તે કોષ ટી પગલાં પછી જીવંત છે? LZW (અલ્ગોરિધમ) (1978નો દાખલો) ડેટા કમ્પ્રેશન-આપેલ શબ્દમાળાઓ s અને t, શું LZ78 પદ્ધતિ સાથે s ને સંકુચિત કરવાથી શબ્દકોશમાં t ઉમેરાઈ જશે? (નોંધ લો કે Gzip જેવા LZ77 સંકોચન માટે, આ ખૂબ સરળ છે, કારણ કે સમસ્યા "Is t in s?".) આંશિક પ્રકારો માટે અનુમાન લખો-લેમ્બડા કલનમાંથી બિન-ટાઇપ કરેલ શબ્દને જોતાં, નક્કી કરો કે આ શબ્દનો આંશિક પ્રકાર છે કે કેમ. ઉપરની મોટાભાગની ભાષાઓ ઘટાડાની વધુ મજબૂત ધારણાઓ હેઠળ પી-પૂર્ણ છે, જેમ કે એકસમાન ઘણા-એક ઘટાડો, ડી. એલ. ઓ. જી. ટી. આઈ. એમ. ઇ. ઘટાડો અથવા પોલિલોગેરિધમિક અંદાજો. પી માં આપેલ સમસ્યા પી-પૂર્ણ છે તે સાબિત કરવા માટે, સામાન્ય રીતે કોઈ જાણીતી પી-પૂર્ણ સમસ્યાને આપેલ સમસ્યામાં ઘટાડવાનો પ્રયાસ કરે છે. 1999માં, જિન-યી કાઈ અને ડી. સિવકુમારે ઓગીહારાના કાર્યને આધારે દર્શાવ્યું હતું કે જો કોઈ વિરલ ભાષા અસ્તિત્વમાં હોય જે પી-પૂર્ણ હોય, તો એલ = પી. પી.-પૂર્ણ સમસ્યાઓ વિવિધ સમયની જટિલતાઓ સાથે ઉકેલી શકાય છે. દાખલા તરીકે, સર્કિટ મૂલ્ય સમસ્યાને ટોપોલોજિકલ સૉર્ટ દ્વારા રેખીય સમયમાં ઉકેલી શકાય છે. અલબત્ત, કારણ કે પી-પૂર્ણ સમસ્યામાં ઘટાડામાં વિવિધ સમયની જટિલતાઓ હોઈ શકે છે, આ હકીકતનો અર્થ એ નથી કે પીની તમામ સમસ્યાઓ પણ રેખીય સમયમાં ઉકેલી શકાય છે. કેટલીક એન. પી.-સમસ્યાઓ એન. પી.-પૂર્ણ અથવા પી. તરીકે જાણીતી નથી. આ સમસ્યાઓ (દા. ત. પી.-પૂર્ણ) ફેક્ટરીંગ, ગ્રાફ આઇસોમોર્ફિઝમ, પેરિટી ગેમ્સ) મુશ્કેલ હોવાની શંકા છે. તેવી જ રીતે પી માં એવી સમસ્યાઓ છે જે પી-પૂર્ણ અથવા એન. સી. તરીકે જાણીતી નથી, પરંતુ તેને સમાંતર બનાવવી મુશ્કેલ હોવાનું માનવામાં આવે છે. ઉદાહરણોમાં બે સંખ્યાઓનો સૌથી મોટો સામાન્ય ભાજક શોધવાના નિર્ણય સમસ્યા સ્વરૂપો, બે સંખ્યાઓ આપવામાં આવે ત્યારે વિસ્તૃત યુક્લિડિયન અલ્ગોરિધમ કયા જવાબ આપશે તે નક્કી કરવા અને મોટા પૂર્ણાંક વજન સાથે આલેખના મહત્તમ વજન મેળની ગણતરીનો સમાવેશ થાય છે. નોંધો સંદર્ભો ગ્રીનલો, રેમન્ડ, જેમ્સ હૂવર અને વોલ્ટર રુઝો. 1995 માં. સમાંતર ગણતરીની મર્યાદાઓ; પી-પૂર્ણતા સિદ્ધાંત. . - સિદ્ધાંત વિકસાવે છે, પછી 96 પી-પૂર્ણ સમસ્યાઓ સૂચિબદ્ધ કરે છે. સાતોરુ મિયાનો, શુજી શિરાઇશી અને તાકાયોશી શૌદાઈ. પી-પૂર્ણ સમસ્યાઓની યાદી. ક્યુશુ યુનિવર્સિટી, RIFIS-TR-CS-17. ડિસેમ્બર 1990. જટિલતા વર્ગો