
aine. ell.-purn

sanganakeey guntaguntichya siddhantat, aine. ell.-complete haah eka guntagunticha varg aahe jyamadhye aine. ell. sathee purn asalelya bhasha aahet, nirnay samasyancha varg joou logridmic memory spacecha vapar karoon nonditormistic turing mashindware sodavala jaau shakato. aine. ell. madheel aine. ell.-purn bhasha yaa sarvat katheen kinwa abhivyakti samasya aahet. laghuganak smrutee jaaget konatyahi aine. ell.-purn samasyanpaiki eka sodavanyasathi jarr eka nirdharak algoridam astitvat asel, tarr aine. ell. = ell.
vyakhya.
aine. ell. madhye nirnay ghenyachya samasya asatat jyaa keval vachanyayogya input tape aanee swatantra vachanyayogya tapes anirdharit turing mashindware sodavalya jaau shakatat jyacha aakar input lambichya laghuganakachya pramananusar maryadit asato. tyachpramane, l madhye asha bhasha asatat jyaa tepchya lambibaddal samaan gruhitkansah nirdharak turing mashindware sodavalya jaau shakatat. kaaran yaa yantranchya bhinn sanrachananchi bahupadi sankhya fakt aahe, l aanee nl heey donhi nishchit bahupadi-velechya nirnay samasyanchya varg p chey upasanch aahet.
aupcharikpane, jevha tee aine. ell. chee asate tevha nirnay samasya aine. ell.-purn asate aanee tyat atirikt gunadharm asato qee aine. ell. madheel itar pratyek nirnay samasya tyat qamee kelee jaau shakate. anyatha nirdisht kelyashivay, yaa vyakhyetil kapat hii nishchit laghuganak-avkash algoridamdware anek-eka kapat asalyache manale jaate.
malmatta.
jarr aine. ell.-purn bhasha 'ex' hii elshi sambandhit asel, tarr aine. ell. madheel itar pratyek bhasha 'vaay' dekhil tashich asel. kaaran, samaja (aine. ell.-purnatenusar) eka nishchit logspace qamee "aar" astitvat aahe, jeey samasya "vaay" chya udaharanala samasya "ex" chya udaharanala "ex" madhye mapp karate aanee ("ex" ell madhye aahe yaa gruhitkadvare) qee samasya sodavanyasathi "aii" "nishchit logspace algoridam astitvat aahe" ex ". yaa gruhitkansah, y bhashetil "y" hii samasya logridmic spacemadhye eka algoridamdware sodavali jaau shakate, jeey input "r" ("y") vareel algoridam "a" chya vartanache anukaran karate, qamee karnyachya algoridamcha vapar karoon "r" ("y") sathee keval-vachaniy tepmadhye pratyek praveshache anukaran karate. 
immerman-zelepseni prameyanusar, jarr ekhadi bhasha saha-aine. ell.-purn asel (mhanje, jarr tiche purak aine. ell.-purn asel) tarr tee bhasha dekhil swatah aine. ell.-purn aahe.
udaharane.
eka mahattvachi aine. ell.-purn samasya mhanje ess. tii.-connectivity (kinwa "pohochanyayogyata") (papadimetrio 1994 tii. aar. emm.). 16.2), tyaa aalekhavar nirdeshit aalekh "jee" aanee done nodes "ess" aanee "tii" dile tarr, "ess" teey "tii" paryantcha marg aahe qee nahee heey nirdharit karanyachi samasya. ess. tii.-jodani aine. ell. madhye asalyache disun yete, kaaran aapan node "ess" pasoon suruvat karato aanee pratyek itar pohochanyayogy nodavar vinanirdharitpane chalato. itar konatyahi aine. ell. algoridamchya sanganakeey sthitee aalekhavar vichar karoon aanee prarambhik avasthepasun swikararh avastheparyantcha (nirdharit) marg asel tarach itar algoridam sweekarel heey lakshat gheuun ess. tii.-jodani aine. ell.-haard asalyache pahile jaau shakate.
dusari mahattvachi aine. ell.-purn samasya mhanje 2-samadhan (papadimetrio 1994 tii. aar. emm.). 16.3), prati khand done chalansah sanyugma samanya swarupat booliyan sootra samadhankarak aahe qee nahee heey nirdharit karanyachi samasya.
dilelya chull-lambichya sanketachya adviteey arthaghatanakshamatechi samasya saha-aine. ell.-purn asalyache darshavile gele; rayatarne heey darshavinyasathi sardinas-patterson algoridamcha eka prakar vaparla qee purak samasya, anek sandigdha decoding asaleli string shodhane, aine. ell. chee aahe. immerman-zelepseni prameyamule, teey asey darshavate qee adviteey deciferability dekhil aine. ell.-purn aahe.
prastavanatmak tarkshastra, bijganit, resheey pranali, aalekh, maryadit svayamchalitataa, sandarbh-mukt vyakaran yaa vishayanvaril atirikt purn samasya johns (1976) madhye soochibaddha aahet.