Unary language
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, યુનરી લેંગ્વેજ અથવા ટેલી લેંગ્વેજ એ ઔપચારિક ભાષા (શબ્દમાળાઓનો સમૂહ) છે જ્યાં તમામ શબ્દમાળાઓ 1k સ્વરૂપ ધરાવે છે, જ્યાં "1" કોઈપણ નિશ્ચિત પ્રતીક હોઈ શકે છે. ઉદાહરણ તરીકે, ભાષા {1,111,1111} યુનરી છે, જેમ કે ભાષા {1k | k એ પ્રાઇમ છે}. આવી તમામ ભાષાઓના જટિલતા વર્ગને કેટલીકવાર TALLY કહેવામાં આવે છે. "યુનરી" નામ એ હકીકત પરથી આવ્યું છે કે યુનરી ભાષા એ યુનરી અંક પ્રણાલીમાં કુદરતી સંખ્યાઓના સમૂહનું એન્કોડિંગ છે. કોઈપણ મર્યાદિત મૂળાક્ષર પર શબ્દમાળાઓનું બ્રહ્માંડ ગણતરીપાત્ર સમૂહ હોવાથી, દરેક ભાષાને કુદરતી સંખ્યાઓના અનન્ય સમૂહ A સાથે મેપ કરી શકાય છે; આમ, દરેક ભાષામાં એક એકીકૃત સંસ્કરણ {A માં 1k | k} હોય છે. તેનાથી વિપરીત, દરેક યુનરી ભાષામાં વધુ સઘન દ્વિસંગી સંસ્કરણ હોય છે, જે કુદરતી સંખ્યાઓ k ના દ્વિસંગી સંકેતલિપીનો સમૂહ છે જેમ કે ભાષામાં 1k છે. જટિલતાને સામાન્ય રીતે ઇનપુટ સ્ટ્રિંગની લંબાઈના સંદર્ભમાં માપવામાં આવે છે, તેથી ભાષાનું યુનરી સંસ્કરણ મૂળ ભાષા કરતાં "સરળ" હોઈ શકે છે. ઉદાહરણ તરીકે, જો કોઈ ભાષાને ઓ (2એન) સમયમાં ઓળખી શકાય છે, તો તેનું યુનરી સંસ્કરણ ઓ (એન) સમયમાં ઓળખી શકાય છે, કારણ કે એન ઝડપથી મોટું થઈ ગયું છે. વધુ સામાન્ય રીતે, જો કોઈ ભાષાને ઓ (એફ (એન)) સમય અને ઓ (જી (એન)) જગ્યામાં ઓળખી શકાય, તો તેના યુનરી સંસ્કરણને ઓ (એન + એફ (લોગ એન)) સમય અને ઓ (જી (લોગ એન)) જગ્યામાં ઓળખી શકાય છે. જો કે, જો કોઈ ભાષામાં સભ્યપદ અનિર્ણિત હોય, તો તેના એકીકૃત સંસ્કરણમાં સભ્યપદ પણ અનિર્ણિત છે. અન્ય જટિલતા વર્ગો સાથેના સંબંધો TALLY એ પી/પોલીમાં સમાયેલ છે-એવી ભાષાઓનો વર્ગ કે જેને બહુપદી સમયમાં ઓળખી શકાય છે, સલાહ કાર્ય આપવામાં આવે છે જે ફક્ત ઇનપુટ લંબાઈ પર આધાર રાખે છે. આ કિસ્સામાં, જરૂરી સલાહ કાર્ય ખૂબ જ સરળ છે-તે દરેક ઇનપુટ લંબાઈ k માટે એક બીટ આપે છે જે સ્પષ્ટ કરે છે કે 1k ભાષામાં છે કે નહીં. યુનરી ભાષા આવશ્યકપણે એક વિરલ ભાષા છે, કારણ કે દરેક n માટે તે લંબાઈ n નું મહત્તમ એક મૂલ્ય ધરાવે છે અને લંબાઈના મહત્તમ n મૂલ્યો પર મહત્તમ n ધરાવે છે, પરંતુ તમામ વિરલ ભાષાઓ યુનરી નથી; આમ TALLY એ SPARSE માં સમાયેલ છે. એવું માનવામાં આવે છે કે કોઈ એન. પી.-હાર્ડ યુનરી ભાષાઓ નથીઃ જો કોઈ યુનરી ભાષા અસ્તિત્વમાં હોય જે એન. પી.-પૂર્ણ હોય, તો પી = એન. પી. આ પરિણામ વિરલ ભાષાઓમાં વિસ્તૃત કરી શકાય છે. જો L એ યુનરી ભાષા છે, તો L * (L નો ક્લેન તારો) એક નિયમિત ભાષા છે. ટેલી વર્ગો જટિલતા વર્ગ P1 એ યુનરી ભાષાઓનો વર્ગ છે જેને બહુપદી સમય ટ્યુરિંગ મશીન દ્વારા ઓળખી શકાય છે (તેના ઇનપુટને યુનરીમાં લખવામાં આવે છે); તે વર્ગ P નું એનાલોગ છે. ગણતરી વર્ગ #P 1, #P નું એનાલોગ પણ જાણીતું છે. સંદર્ભ નોંધો સામાન્ય સંદર્ભો લાન્સ ફોર્ટનો. મનપસંદ પ્રમેયોઃ નાના સમૂહો. એપ્રિલ 18,2006. http://weblog.fortnow.com/2006/04/favorite-theorems-small-sets.html ઔપચારિક ભાષાઓ કોમ્પ્યુટેશનલ જટિલતા સિદ્ધાંત