Sparse language
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, વિરલ ભાષા એ એક ઔપચારિક ભાષા (શબ્દમાળાઓનો સમૂહ) છે, જેમ કે ભાષામાં n લંબાઈના શબ્દમાળાઓની સંખ્યાની ગણતરી કરતી જટિલતા કાર્ય, n ના બહુપદી કાર્ય દ્વારા બંધાયેલ હોય છે. તેનો ઉપયોગ મુખ્યત્વે અન્ય વર્ગો સાથે જટિલતા વર્ગ NP ના સંબંધના અભ્યાસમાં થાય છે. તમામ વિરલ ભાષાઓના જટિલતા વર્ગને સ્પાર્સ કહેવામાં આવે છે. વિરલ ભાષાઓને વિરલ કહેવામાં આવે છે કારણ કે ત્યાં લંબાઈ n ના કુલ 2n શબ્દમાળાઓ હોય છે, અને જો કોઈ ભાષામાં માત્ર બહુપદીમાં આમાંના ઘણા હોય, તો તેમાં n લંબાઈના શબ્દમાળાઓનું પ્રમાણ ઝડપથી શૂન્ય થાય છે કારણ કે n વધે છે. તમામ યુનારી ભાષાઓ વિરલ છે. બિન-તુચ્છ વિરલ ભાષાનું ઉદાહરણ એ દ્વિસંગી શબ્દમાળાઓનો સમૂહ છે જે અમુક નિશ્ચિત k માટે બરાબર k1 બિટ્સ ધરાવે છે; દરેક n માટે, ભાષામાં માત્ર શબ્દમાળાઓ હોય છે, જે nk દ્વારા બંધાયેલ હોય છે. અન્ય જટિલતા વર્ગો સાથેના સંબંધો SPARSE માં TALLY નો સમાવેશ થાય છે, જે યુનરી ભાષાઓનો વર્ગ છે, કારણ કે તેમાં કોઈપણ એક લંબાઈની મહત્તમ એક સ્ટ્રિંગ હોય છે. પી/પોલીમાં તમામ ભાષાઓ વિરલ ન હોવા છતાં, પી/પોલીમાં કોઈપણ ભાષાથી વિરલ ભાષામાં બહુપદી-સમય ટ્યુરિંગ ઘટાડો છે. ફોર્ચ્યુને 1979માં દર્શાવ્યું હતું કે જો કોઈ વિરલ ભાષા સહ-એન. પી.-પૂર્ણ હોય, તો પી = એન. પી.; મહાનેએ 1982માં બતાવવા માટે આનો ઉપયોગ કર્યો હતો કે જો કોઈ વિરલ ભાષા એન. પી.-પૂર્ણ હોય, તો પી = એન. પી. (આ મહાનેની પ્રમેય છે). ડાબી બાજુના સેટના આધારે આનો એક સરળ પુરાવો 1991માં ઓગીહારા અને વાતાનાબે દ્વારા આપવામાં આવ્યો હતો. મહાનીની દલીલમાં ખરેખર વિરલ ભાષાને એન. પી. માં હોવાની જરૂર નથી (કારણ કે એન. પી.-હાર્ડ વિરલ સમૂહનું અસ્તિત્વ એન. પી.-પૂર્ણ વિરલ સમૂહનું અસ્તિત્વ સૂચવે છે), તેથી જો અને માત્ર પી = એન. પી. હોય તો જ વિરલ એન. પી.-હાર્ડ સમૂહ હોય છે. વધુમાં, જો અને માત્ર ત્યારે જ જો એન. પી. માં વિરલ ભાષાઓ અસ્તિત્વમાં હોય જે પી. માં ન હોય, તો એન. પી.-પૂર્ણ ભાષામાંથી વિરલ ભાષામાં ટ્યુરિંગ ઘટાડો (મહાનીના પ્રમેયમાંથી કાર્પ ઘટાડાના વિરોધમાં) થાય છે. 1999માં, જિન-યી કાઈ અને ડી. સિવકુમારે ઓગીહારાના કામ પર નિર્માણ કરતા દર્શાવ્યું હતું કે જો વિરલ પી-પૂર્ણ સમસ્યા અસ્તિત્વમાં હોય, તો એલ = પી. સંદર્ભો બાહ્ય લિંક્સ લાન્સ ફોર્ટનો. મનપસંદ પ્રમેયોઃ નાના સમૂહો. એપ્રિલ 18,2006. વિલિયમ ગેસાર્ક. સ્પાર્સ સેટ્સ (મહાનીને શ્રદ્ધાંજલિ). 29 જૂન, 2007. ઔપચારિક ભાષાઓ કોમ્પ્યુટેશનલ જટિલતા સિદ્ધાંત