Geri Dön

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

  1. Tez No: 652240
  2. Yazar: MEHMET UTKAN GEZER
  3. Danışmanlar: PROF. AHMET CELAL CEM SAY
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2020
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. The complexity of debate checking

    Münazara kontrolünün karmaşıklığı

    HÜSEYİN GÖKALP DEMİRCİ

    Yüksek Lisans

    İngilizce

    İngilizce

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AHMET CELAL CEM SAY

  2. Fraktal geometri ve hidrolik pürüzlülük

    The Fractal geometry and the hydraulic roughness

    SAİT ALANSATAN

    Yüksek Lisans

    Türkçe

    Türkçe

    1991

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    PROF.DR. CAHİT ÖZGÜR

  3. İ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

    Doktora

    Türkçe

    Türkçe

    2014

    İşletmeHaliç Üniversitesi

    İşletme Ana Bilim Dalı

    YRD. DOÇ. DR. SELVA STAUB

  4. Kaos analizi: Bir finansal sektör uygulaması

    Başlık çevirisi yok

    CAFER ERCAN BOZDAĞ

    Doktora

    Türkçe

    Türkçe

    1998

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET HALUK ERKUT

  5. Performance analysis of relay aided terahertz systems

    Röle destekli terahertz haberleşme sistemlerinin performans analizi

    BENGÜ BİLGİÇ

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ SEMİHA TEDİK BAŞARAN