Tanımlayıcı karmaşıklık teorisi - Descriptive complexity theory

Tanımlayıcı karmaşıklık , karmaşıklık sınıflarını içlerindeki dilleri ifade etmek için gereken mantık türüne göre karakterize eden hesaplama karmaşıklığı teorisinin ve sonlu model teorisinin bir dalıdır . Örneğin , polinom hiyerarşisindeki tüm karmaşıklık sınıflarının birleşimi olan PH , tam olarak ikinci dereceden mantık ifadeleriyle ifade edilebilen dillerin sınıfıdır . Karmaşıklık ve sonlu yapıların mantığı arasındaki bu bağlantı, sonuçların bir alandan diğerine kolayca aktarılmasını sağlar, yeni ispat yöntemlerini kolaylaştırır ve ana karmaşıklık sınıflarının bir şekilde "doğal" olduğuna ve kullanılan belirli soyut makinelere bağlı olmadığına dair ek kanıtlar sağlar. onları tanımlamak için.

Spesifik olarak, her mantıksal sistem , içinde ifade edilebilen bir dizi sorgu üretir . Sorgular – sonlu yapılarla sınırlandırıldığında – geleneksel karmaşıklık teorisinin hesaplama problemlerine karşılık gelir .

Tanımlayıcı karmaşıklığın ilk ana sonucu, 1974'te Ronald Fagin tarafından gösterilen Fagin teoremiydi . NP'nin tam olarak varoluşçu ikinci derece mantığın cümleleri ile ifade edilebilen diller kümesi olduğunu belirledi ; yani, ilişkiler, fonksiyonlar ve alt kümeler üzerinde evrensel nicelemeyi hariç tutan ikinci dereceden mantık. Diğer birçok sınıf daha sonra, çoğu Neil Immerman tarafından bu şekilde karakterize edildi :

• Birinci mertebeden mantık , AC ^0'a karşılık gelen FO sınıfını tanımlar; bu , sabit zamanda eşzamanlı bir rastgele erişim makinesi tarafından tanınan dillere eşit olan, sınırlı derinlikteki polinom boyutlu devreler tarafından tanınan dillerdir .
• Değişmeli, geçişli bir kapatma operatörü eklenmiş birinci dereceden mantık , logaritmik uzayda çözülebilen problemler olan L'ye eşit olan SL verir .
• Bir ile Birinci derece mantık Geçişli kapatma operatörü verir NL nondeterministic logaritmik uzayda çözülebilir sorunlar.
• Doğrusal mertebenin varlığında, en az sabit nokta operatörlü birinci mertebeden mantık , deterministik polinom zamanında çözülebilen problemler olan P'yi verir .
• Varoluşsal ikinci dereceden mantık NP verir .
• Evrensel ikinci dereceden mantık (varoluşsal ikinci dereceden niceleme hariç) eş-NP verir.
• İkinci dereceden mantık , yukarıda belirtildiği gibi PH'ye karşılık gelir .
• Geçişli kapanışlı (değişmeli veya değil) ikinci dereceden mantık , polinom uzayında çözülebilen problemler olan PSPACE'i verir .
• En az sabit nokta operatörlü ikinci dereceden mantık , üstel zamanda çözülebilen problemler olan EXPTIME'ı verir .
• ${\displaystyle \var {\color {Blue}{\mathsf {HO}}}^{i}}$, i sırasının varoluşsal niceleyicisi ve ardından bir sıra formülüne sahip mantık eşittir${\görüntüleme stili i-1}$${\displaystyle {\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{O(1)}))}$
• ${\displaystyle {\mathsf {HO}}_{j}^{i}={\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{ O(1)}))^{\Sigma _{j}^{\mathsf {P}}}}$
• HO eşittir ELEMENTARY

Ayrıca bakınız

• SO (karmaşıklık)
• FO (karmaşıklık)
• Bir cümlenin spektrumu

Referanslar

• Ronald Fagin , Genelleştirilmiş Birinci Dereceden Spektrumlar ve Polinom Zamanında Tanınan Kümeler . Hesaplamanın Karmaşıklığı , ed. R. Karp, SIAM-AMS Proceedings 7, s. 27–41. 1974.
• Fagin, Ronald (1993). "Sonlu model teorisi - kişisel bir bakış açısı" . Teorik Bilgisayar Bilimi . 116 : 3-31. doi : 10.1016/0304-3975(93)90218-i .
• Immerman, Neil (1983). "Karmaşıklık sınıflarını yakalayan diller". Hesaplama Teorisi Üzerine On Beşinci Yıllık ACM Sempozyumu Tutanakları - STOC '83 . s. 347–354. doi : 10.1145/800061.808765 . ISBN'si 0897910990.
• Immerman, Neil (1999). Tanımlayıcı Karmaşıklık . New York: Springer-Verlag. s. 113–119. ISBN'si 0-387-98600-6..

daha fazla okuma

• Shawn Hedman, Mantıkta ilk ders: model teorisi, ispat teorisi, hesaplanabilirlik ve karmaşıklığa giriş , Oxford University Press, 2004, ISBN  0-19-852981-3 , bölüm 10.3 lisans öğrencileri için uygun bir giriştir
• Gradel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel ; Vardi, Moşe Y .; Venema, Yde; Weinstein, Scott (2007). Sonlu model teorisi ve uygulamaları . Teorik Bilgisayar Bilimlerinde Metinler. Bir EATCS Serisi. Berlin: Springer-Verlag . ISBN'si 978-3-540-00428-8. Zbl  1133.03001 .

Dış bağlantılar

• Bir diyagram dahil Neil Immerman'ın açıklayıcı karmaşıklık sayfası