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ı: 45
Ö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
- The complexity of debate checking
Münazara kontrolünün karmaşıklığı
HÜSEYİN GÖKALP DEMİRCİ
Yüksek Lisans
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET CELAL CEM SAY
- Fraktal geometri ve hidrolik pürüzlülük
The Fractal geometry and the hydraulic roughness
SAİT ALANSATAN
- İnovatif ve negatif entropik stratejilerin kurumsal kimliğe etkisi üzerine bir uygulama
A practice about the effects of innovative and negative entropic strategies on corporate identity
TARKAN GÖK
- Kaos analizi: Bir finansal sektör uygulaması
Başlık çevirisi yok
CAFER ERCAN BOZDAĞ
Doktora
Türkçe
1998
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET HALUK ERKUT
- Performance analysis of relay aided terahertz systems
Röle destekli terahertz haberleşme sistemlerinin performans analizi
BENGÜ BİLGİÇ
Yüksek Lisans
İngilizce
2024
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ SEMİHA TEDİK BAŞARAN