Sonlu hafıza ve sonlu rastgelelik kullanan, alabildiğine küçük katı tip hatalı doğrulayıcılar

İşbu çalışmada, girdinin boyutundan bağımsız, sabit bir miktarda yazı-tura atma hakkı tanınan sonlu hal hesaplayıcılarının, aidiyet ispatlarını doğrulama konusunda yapabileceklerinin sınırlarını inceliyoruz. Cem Say ve Abuzer Yakaryılmaz'ın önceki bir çalışmada ispatladığı üzere, bu nitelikteki hesaplayıcıların katı tipte 1/2'den az hata yaparaktan doğrulayabildikleri dillerin kümesi, tam da NL sınıfına denk gelmektedir. Fakat bu ispatta sunulan doğrulayıcıların katı tip hatası, NL'nin büyük çoğunluğu için 1/2'ye oldukça yakın çıkmakta. Bu tezde bu zayıf türden hesaplayıcıların alabildiğine küçük katı tip hata ile doğrulayabildiği dilleri, NL sınıfının bir alt kümesi olarak belirliyoruz. Pozitif herhangi bir e değeri için, doğrusal zamanda çalışan çok kafalı bir belirsiz sonlu hal hesaplayıcısı (2nfa(k)) ile tanınabilen herhangi bir dili tanıyan, sonlu hafıza ve sonlu rastgelelik kullanan ve katı tip hatası en fazla e olan bir doğrulayıcı inşa eden bir yöntem sunuyoruz. Bu yöntemi tüm NL'ye genellemenin neden zor olduğunu tartışıyor, doğrusal zamanda çalışan 2nfa(k)'lerin dil tanıma gücünün, aynı anda zaman ve de hafıza sınırlarına tabi Turing makineleri üzerinden tanımlanmış karmaşıklık sınıfları ile olan alakasını hayli sıkı bir biçimde kuruyoruz.