The complexity of debate checking
Münazara kontrolünün karmaşıklığı
- Tez No: 338818
- Danışmanlar: PROF. DR. 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: 2013
- 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ı: 73
Özet
Bu tezde ispatçı ve çürütücü adlı iki oyuncunun girdinin dil içinde olup olmadığı üzerine oluşturduğu diyoloğun sınırlı kaynaklı olasılıksal bir hakem tarafından okunduğu yeni bir münazara modeli tanımlanmaktadır. Modelimiz tek yönlü etkileşimli ispat sistemleri, noksan bilgili oyunlar ve olasılıksal kontrollü münazara modellerini birleştirir ve genelleştirir. Tam-, kısmi- ve sıfır-bilgili münazara çeşitleri ele alınmaktadır. Kısmi- ve sıfır-bilgili münazaralarda ispatçı çürütücünün mesajlarından sırayla bazılarını ve hiçbirini göremezken, tam-bilgili münazaralarda her iki oyuncu da birbirlerinin mesajlarını tamamen görürler. Zamansal, belleksel ve olasılıksal olarak sınırlı bir hakemin bu çeşitlerde münzaraları kontrol ederek hangi dil ailelerini tanıyabileceği araştırılmaktadır. O(1) bellek ve O(1) rastgelelik kullanan hakemlerin bu üç münazara çeşidi için tanıyabildiği dil sınıflarının tam tanımı yapılmaktadır. İlaveten, sonlu bellekli hakemler tarafından herhangi bir hata payı ile kontrol edilebilen sırasıyla sıfır- ve kısmi-bilgili münazaralara sahip diller kümesi için alt limitler verilmektedir. Tam- ve kısmi-bilgili münazaraların zaman-sınırlı hakemler tarafından kontrol edildiği durumun gücü de araştırıldı ve bu hakemlerin ne kadar rastgelelik kullanırlarsa kullansınlar aynı sınırlara sahip belirlenimci hakemlere bir üstünlük kuramadıkları anlaşıldı. Fakat, rastgelelik kullanılmasının bu zaman-sınırlı hakemlerin beleklerinin zaman-sınırının logaritmasına kadar indirilebilmesine izin verdiği ortaya çıktı. Ayrıca, polinom zaman ve logaritmik bellekle sınırlı hakemlerin PSPACE'teki diller için tam- ve kısmi-bilgili münazara kontrol etmesinin logaritmik rastgelelik kullanılarak da mümkün olduğu gösterilmektedir. Son olarak, polinom zaman ve logaritmik bellek kullanıp tam-bilgili münazara kontrol eden hakemlerin yapısından faydalanıp böyle münazaralara sahip dillerin nicellendirilmiş matrisler üzerinde maksimum çarpım problemine indirgenebileceği gösterilerek bu problemin yakınsanamazlığı ile ilgili bir sonuç sunulmaktadır.
Özet (Çeviri)
We introduce a model of probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. Our model combines and generalizes the concepts of one-way interactive proof systems, games of incomplete information, and probabilistically checkable complete-information debate systems. We consider debates of partial- and zero-information, where the prover is prevented from seeing some or all of the messages of the refuter, as well as those of complete-information. The classes of languages with debates checkable by verifiers operating under severe bounds on the time, memory, and randomness are studied. We give full characterizations of versions of these classes corresponding to simultaneous bounds of O(1) space and O(1) random bits, and logarithmic space and O(1) random bits. We further examine the power of constant-space model by giving lower bounds for the classes of languages checkable by such verifiers for any desired error bound when we loosen the randomness bound. We also examine the power of debate checking by time-bounded verifiers and show that no amount of randomness can help a time-bounded verifier to outperform its deterministic counterpart. However, we show that randomness does seem to help when we further constrain these time-bounded verifiers to use only logarithmic space in the order of their time bound. Additionally, in case of logspace and polynomial-time verifiers, we show that logarithmic randomness is sufficient to check complete- and partial-information debates for the languages in PSPACE. Finally, we show that any language having debates checkable by logspace polynomial-time verifiers can be reduced to the quantified max word problem for matrices, which allows us to present a result on the hardness of approximating this problem.
Benzer Tezler
- Modern liderlik kuramları bağlamında seçmenlerin politik liderlik stillerine yönelik duygu ve tutumlarının incelenmesi
Investigation of voter's emotions and attitudes too political leadership styles in the context of modern leadership theories
ALİ RUHAN ÇELİK
Doktora
Türkçe
2023
PsikolojiÜsküdar ÜniversitesiPsikoloji Bilim Dalı
PROF. DR. DENİZ ÜLKE ARIBOĞAN
PROF. DR. GÖKBEN HIZLI SAYAR
- Le probleme identitaire et la representation de l'autrui dans les romans de Marguerite Duras
Marguerite Duras'ın romanlarında kimlik sorunu ve ötekinin temsili
LALE ERDEM
Yüksek Lisans
Fransızca
2024
Fransız Dili ve EdebiyatıSelçuk ÜniversitesiFransız Dili ve Edebiyatı Ana Bilim Dalı
DOÇ. DR. AHMET GÖGERCİN
- Türkiye denetim standartları kapsamında bağımsız denetimin sonuçları ve raporlanması üzerine bir araştırma
A research on the results and reporting of independent auditing in the Turkish auditing standards
SEDA BAHŞI
Yüksek Lisans
Türkçe
2019
İşletmeDokuz Eylül Üniversitesiİşletme Ana Bilim Dalı
PROF. DR. FATMA TEKTÜFEKÇİ
- Ermeni tehcirini anlatmak: 2015 yılında Türkiye, Ermenistan, Lübnan ve Fransa'da okutulan lise tarih ders kitapları üzerine karşılaştırmalı bir analiz
Narrating the deportation of Armenians: A comparative study of the history textbooks of secondary education in Turkey, Armenia, France, and Lebanon (2015)
ÖYKÜ GÜRPINAR
Doktora
Türkçe
2020
Eğitim ve ÖğretimMimar Sinan Güzel Sanatlar ÜniversitesiGenel Sosyoloji ve Metodoloji Ana Bilim Dalı
PROF. DR. ŞÜKRÜ ASLAN
- Mimari tasarımın şiddeti ve karşı stratejiler
Violence of architectural design and counter strategies
TUĞÇE ALKAŞ
Yüksek Lisans
Türkçe
2018
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. DR. SIDIKA ASLIHAN ŞENEL