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

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.