Co-NP-complete
જટિલતા સિદ્ધાંતમાં, સહ-એન. પી.-પૂર્ણ કોમ્પ્યુટેશનલ સમસ્યાઓ તે છે જે સહ-એન. પી. માં સૌથી મુશ્કેલ સમસ્યાઓ છે, એ અર્થમાં કે સહ-એન. પી. માં કોઈપણ સમસ્યાને માત્ર બહુપદી ઓવરહેડ સાથે કોઈપણ સહ-એન. પી.-પૂર્ણ સમસ્યાના વિશેષ કેસ તરીકે પુનઃરચના કરી શકાય છે. જો પી સહ-એન. પી. થી અલગ હોય, તો પછી તમામ સહ-એન. પી. પૂર્ણ સમસ્યાઓ બહુપદી સમયમાં ઉકેલી શકાતી નથી. જો સહ-એન. પી.-પૂર્ણ સમસ્યાને ઝડપથી હલ કરવાની કોઈ રીત અસ્તિત્વમાં હોય, તો તે અલ્ગોરિધમનો ઉપયોગ તમામ સહ-એન. પી. સમસ્યાઓને ઝડપથી હલ કરવા માટે થઈ શકે છે. દરેક સહ-એન. પી.-પૂર્ણ સમસ્યા એ એન. પી.-પૂર્ણ સમસ્યાનું પૂરક છે. એન. પી. અને સહ-એન. પી. બંનેમાં કેટલીક સમસ્યાઓ છે, ઉદાહરણ તરીકે પી અથવા પૂર્ણાંક પરિબળમાં તમામ સમસ્યાઓ. જો કે, તે જાણીતું નથી કે સમૂહો સમાન છે કે નહીં, જોકે અસમાનતાને વધુ સંભવિત માનવામાં આવે છે. વધુ વિગતો માટે સહ-એન. પી. અને એન. પી.-પૂર્ણ જુઓ. ફોર્ચ્યુને 1979માં દર્શાવ્યું હતું કે જો કોઈ વિરલ ભાષા સહ-એન. પી.-પૂર્ણ (અથવા તો માત્ર સહ-એન. પી.-સખત) હોય, તો તે મહાનીના પ્રમેય માટે નિર્ણાયક પાયો છે. ઔપચારિક વ્યાખ્યા એક નિર્ણય સમસ્યા સી સહ-એન. પી. પૂર્ણ છે જો તે સહ-એન. પી. માં હોય અને જો સહ-એન. પી. માં દરેક સમસ્યા બહુપદી-સમયની હોય તો તેને ઘણી-એક ઘટાડી શકાય છે. આનો અર્થ એ છે કે દરેક સહ-એન. પી. સમસ્યા L માટે, એક બહુપદી સમય અલ્ગોરિધમ અસ્તિત્વમાં છે જે L ના કોઈપણ ઉદાહરણને સમાન સત્ય મૂલ્ય સાથે C ના ઉદાહરણમાં રૂપાંતરિત કરી શકે છે. પરિણામે, જો આપણી પાસે C માટે બહુપદી સમય અલ્ગોરિધમ હોય, તો આપણે બહુપદી સમયમાં તમામ સહ-NP સમસ્યાઓ હલ કરી શકીશું. ઉદાહરણ સહ-એન. પી.-પૂર્ણ સમસ્યાનું એક ઉદાહરણ ટૉટોલોજી છે, જે આપેલ બુલિયન સૂત્ર એક ટૉટોલોજી છે કે કેમ તે નક્કી કરવાની સમસ્યા છે; એટલે કે, ચલ માટે સાચા/ખોટા મૂલ્યોની દરેક સંભવિત સોંપણી સાચું નિવેદન આપે છે કે કેમ. આ બુલિયન સંતોષકારક સમસ્યા સાથે નજીકથી સંબંધિત છે, જે પૂછે છે કે શું આવી ઓછામાં ઓછી એક સોંપણી અસ્તિત્વમાં છે, અને તે એન. પી.-પૂર્ણ છે. સંદર્ભો બાહ્ય કડીઓ જટિલતા વર્ગો