Berman–Hartmanis conjecture
માળખાકીય જટિલતા સિદ્ધાંતમાં, બર્મન-હાર્ટમેનિસ અનુમાન એ લિયોનાર્ડ સી. બર્મન અને જ્યુરિસ હાર્ટમેનિસના નામ પરથી નામ આપવામાં આવેલ એક વણઉકેલાયેલી ધારણા છે જે જણાવે છે કે તમામ એન. પી.-પૂર્ણ ભાષાઓ એકસરખી દેખાય છે, તે અર્થમાં કે તેઓ બહુપદી સમય સમરૂપતા દ્વારા એકબીજા સાથે સંબંધિત હોઈ શકે છે. ઔપચારિક ભાષાઓ L1 અને L2 વચ્ચેની સમરૂપતા એ L1 ના મૂળાક્ષરમાં શબ્દમાળાઓથી લઈને L2 ના મૂળાક્ષરમાં શબ્દમાળાઓ સુધીનો એક બાયજેક્ટિવ નકશો છે, જેમાં એ ગુણધર્મ છે કે જો f (x) L2 સાથે સંબંધિત હોય તો જ x શબ્દમાળા L1 સાથે સંબંધિત છે. તે બહુપદી સમય આઇસોમોર્ફિઝમ (અથવા ટૂંકા માટે પી-આઇસોમોર્ફિઝમ) છે જો એફ અને તેના વ્યસ્ત વિધેય બંનેને તેમની દલીલોની લંબાઈમાં સમય બહુપદીની માત્રામાં ગણતરી કરી શકાય. અવલોકન કરવામાં આવ્યું હતું કે તે સમયે એન. પી.-પૂર્ણ તરીકે ઓળખાતી તમામ ભાષાઓ પી-આઇસોમોર્ફિક હતી. વધુ મજબૂત રીતે, તેઓએ અવલોકન કર્યું કે તે સમયની તમામ જાણીતી એન. પી.-પૂર્ણ ભાષાઓ પેડ કરવા યોગ્ય હતી, અને તેઓએ સાબિત કર્યું (માયહિલ આઇસોમોર્ફિઝમ પ્રમેયની જેમ) કે પેડ કરવા યોગ્ય એન. પી.-પૂર્ણ ભાષાઓની તમામ જોડીઓ પી.-આઇસોમોર્ફિક છે. જો બહુપદી સમય કાર્ય f (x, y) બહુપદી સમય વ્યુત્ક્રમ સાથે હોય અને ગુણધર્મ સાથે કે, બધા x અને y માટે, x એ L સાથે સંબંધિત હોય તો અને માત્ર જો f (x, y) L સાથે સંબંધિત હોય તો L: એટલે કે, ઇનપુટ x ને અપ્રસ્તુત માહિતી y સાથે, ઉલટાવી શકાય તેવી રીતે, ભાષામાં તેનું સભ્યપદ બદલ્યા વિના પેડ કરવું શક્ય છે. આ પરિણામોના આધારે, બર્મન અને હાર્ટમેનિસે અનુમાન લગાવ્યું હતું કે તમામ એન. પી.-પૂર્ણ ભાષાઓ પી-આઇસોમોર્ફિક છે. પી-આઇસોમોર્ફિઝમ પેડબિલિટી જાળવી રાખે છે, અને ત્યાં પેડબલ એન. પી.-પૂર્ણ ભાષાઓ અસ્તિત્વમાં છે, બર્મન-હાર્ટમેનિસ અનુમાન દર્શાવવાની સમકક્ષ રીત એ છે કે તમામ એન. પી.-પૂર્ણ ભાષાઓ પેડબલ છે. બહુપદી સમય સમરૂપતા એ એક સમાનતા સંબંધ છે, અને તેનો ઉપયોગ ઔપચારિક ભાષાઓને સમાનતા વર્ગોમાં વિભાજિત કરવા માટે થઈ શકે છે, તેથી બર્મન-હાર્ટમેનિસ અનુમાન દર્શાવવાની બીજી રીત એ છે કે એન. પી.-પૂર્ણ ભાષાઓ આ સંબંધ માટે એક સમાનતા વર્ગ બનાવે છે. અસરો જો બર્મન-હાર્ટમેનિસનો અંદાજ સાચો હોય, તો તેનું તાત્કાલિક પરિણામ વિરલ એન. પી.-પૂર્ણ ભાષાઓનું અસ્તિત્વ ન હોવું હશે, એટલે કે એવી ભાષાઓ કે જેમાં n લંબાઈના હા-ઉદાહરણોની સંખ્યા માત્ર n ના વિધેય તરીકે બહુપદીમાં વધે છે. જાણીતી એન. પી.-પૂર્ણ ભાષાઓમાં સંખ્યાબંધ હા-ઉદાહરણો હોય છે જે ઝડપથી વધે છે, અને જો L એ ઘાતાંકીય રીતે ઘણા હા-ઉદાહરણો ધરાવતી ભાષા હોય તો તે વિરલ ભાષામાં પી-આઇસોમોર્ફિક ન હોઈ શકે, કારણ કે તેના હા-ઉદાહરણોને એક-થી-એક મેપિંગ માટે બહુપદીથી લાંબા કરતાં વધુ હોય તેવા શબ્દમાળાઓ સાથે મેપ કરવા પડશે. વિરલ એન. પી.-પૂર્ણ ભાષાઓનું બિનઅસ્તિત્વ સૂચવે છે કે પી ષ્ણુપ, કારણ કે જો પી = એન. પી. હોય તો પી. માં દરેક બિન-તુચ્છ ભાષા (કેટલીક વિરલ ભાષાઓ સહિત, જેમ કે દ્વિસંગી શબ્દમાળાઓની ભાષા, જેના તમામ બિટ્સ શૂન્ય હોય છે) એન. પી.-પૂર્ણ હશે. 1982માં, સ્ટીવ મહેનીએ તેમનો પુરાવો પ્રકાશિત કર્યો હતો કે વિરલ એન. પી.-પૂર્ણ ભાષાઓનું અસ્તિત્વ (એન. પી.-પૂર્ણતાને પ્રમાણભૂત રીતે ઘણા-એક ઘટાડાનો ઉપયોગ કરીને વ્યાખ્યાયિત કરવામાં આવે છે) હકીકતમાં એ નિવેદનની સમકક્ષ છે કે પી ષ્ણાંક એન. પી.; આ મહાનિનો પ્રમેય છે. ટ્યુરિંગ ઘટાડાનો ઉપયોગ કરીને એન. પી.-પૂર્ણતાની હળવા વ્યાખ્યા માટે પણ, વિરલ એન. પી.-પૂર્ણ ભાષાનું અસ્તિત્વ બહુપદી પદાનુક્રમનું અનપેક્ષિત પતન સૂચવે છે. અનુમાન તરફના પુરાવા તરીકે, પુરાવા દર્શાવે છે કે મર્યાદિત પ્રકારના ઘટાડા સાથે સમાન અનુમાન સાચું છેઃ દરેક બે ભાષાઓ કે જે AC0 ઘણા-એક ઘટાડા હેઠળ NP માટે પૂર્ણ છે તેમાં AC0 આઇસોમોર્ફિઝમ છે. તે દર્શાવે છે કે, જો એક તરફી કાર્યો અસ્તિત્વમાં હોય કે જે તમામ ઇનપુટ્સ પર બહુપદી સમયમાં ઊંધી ન કરી શકાય, પરંતુ જો આવા દરેક કાર્યમાં ઇનપુટ્સનો નાનો પરંતુ ગાઢ સબસેટ હોય કે જેના પર તેને પી/પોલીમાં ઊંધી કરી શકાય (જેમ કે આ પ્રકારના જાણીતા કાર્યો માટે સાચું છે) તો દરેક બે એન. પી.-પૂર્ણ ભાષાઓમાં પી/પોલી આઇસોમોર્ફિઝમ હોય છે. અને એક ઓરેકલ મશીન મોડેલ મળ્યું જેમાં આઇસોમોર્ફિઝમ અનુમાનનું એનાલોગ સાચું છે. અનુમાન સામે પુરાવા અને દ્વારા પૂરા પાડવામાં આવ્યા હતા. જોસેફ અને યંગે એન. પી.-પૂર્ણ સમસ્યાઓનો એક વર્ગ રજૂ કર્યો, કે-સર્જનાત્મક સમૂહો, જેના માટે પ્રમાણભૂત એન. પી.-પૂર્ણ સમસ્યાઓમાં કોઈ પી-આઇસોમોર્ફિઝમ જાણીતું નથી. કર્ટ્ઝ એટ અલ. દર્શાવ્યું કે ઓરેકલ મશીન મોડેલોમાં રેન્ડમ ઓરેકલની ઍક્સેસ આપવામાં આવે છે, તો અનુમાનનું એનાલોગ સાચું નથીઃ જો એ રેન્ડમ ઓરેકલ છે, તો એન. પી. એ. માટે પૂર્ણ થયેલા તમામ સમૂહોમાં પી. એ. માં આઇસોમોર્ફિઝમ્સ નથી. રેન્ડમ ઓરેકલનો ઉપયોગ સામાન્ય રીતે ક્રિપ્ટોગ્રાફીના સિદ્ધાંતમાં ક્રિપ્ટોગ્રાફિક હેશ કાર્યોને મોડેલ કરવા માટે થાય છે જે ગણતરીત્મક રીતે રેન્ડમથી અલગ પાડવા યોગ્ય નથી, અને કર્ટ્ઝ એટ અલનું નિર્માણ. ઓરેકલની જગ્યાએ આવા કાર્ય સાથે કરી શકાય છે. આ કારણોસર, અન્ય લોકો વચ્ચે, ઘણા જટિલતા સિદ્ધાંતવાદીઓ દ્વારા બર્મન-હાર્ટમેનિસ આઇસોમોર્ફિઝમ અનુમાનને ખોટું માનવામાં આવે છે. માળખાકીય જટિલતા સિદ્ધાંત કોમ્પ્યુટર વિજ્ઞાનમાં વણઉકેલાયેલી સમસ્યાઓનું અનુમાન કરે છે ગણિતમાં વણઉકેલાયેલી સમસ્યાઓ