Constant-space, constant-randomness verifiers with arbitrarily small strong error
Sonlu hafıza ve sonlu rastgelelik kullanan, alabildiğine küçük katı tip hatalı doğrulayıcılar
- Tez No: 652240
- Danışmanlar: PROF. AHMET CELAL CEM SAY
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
İş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.
Özet (Çeviri)
We study the capabilities of probabilistic finite-state machines that act as verifiers for certificates of language membership for input strings, in the regime where the verifiers are restricted to toss some fixed nonzero number of coins regardless of the input size. Say and Yakaryılmaz showed that the class of languages that could be verified by these machines within a strong error bound strictly less than 1/2 is precisely NL, but their construction yields verifiers with strong error bounds that are very close to 1/2 for most languages in that class. We characterize a subset of NL for which verification with arbitrarily low strong error is possible by these extremely weak machines. It turns out that, for any e > 0, one can construct a constant-coin, constant-space verifier operating within strong error e for every language that is recognizable by a linear-time multi-head nondeterministic finite automaton (2nfa(k)). We discuss why it is difficult to generalize this method to all of NL, and give a reasonably tight way to relate the power of linear-time 2nfa(k)'s to simultaneous time-space complexity classes defined in terms of Turing machines.
Benzer Tezler
- Bazı esterlerin kinetik incelenmesi ve termodinamik parametrelerin belirlenmesi
Kinetic study and detesmination of thermodnamic parameters of some esters
İBRAHİM TAŞ
Yüksek Lisans
Türkçe
1986
Kimya MühendisliğiUludağ ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. MUSTAFA CEBE
- Kömürdeki piritin giderilmesi ve çözünürleştirme kinetiğinin incelenmesi
Başlık çevirisi yok
YAVUZ ONGANER
- Kurbağa gastrik mukozasında K-H ATPaz enziminin kinetik özellikleri ve oluşturulan ülser modelinde enzim aktivitesi
Başlık çevirisi yok
SEYHAN TÜKEL
- Barajların hacim-verim ilişkisi üzerine bir araştırma
Başlık çevirisi yok
MEHMET KILIÇARSLAN
Yüksek Lisans
Türkçe
1987
İnşaat MühendisliğiÇukurova Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. TEFARUK HAKTANIR
- Sürekli rejim şartlarında nükleer yakıt çubuklarında tek ve iki boyutlu ısı iletiminin analizi
In steady-state conditions analyses of one and two dimensional conduction in nuclear fuel rods
İBRAHİM ATILGAN
Yüksek Lisans
Türkçe
1987
Makine MühendisliğiGazi ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERCAN ATAER