Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde de sıkça kullanılan ve matematiğin bir parçası olan karmaşıklı teorisi (complexity theory) içerisinde tanımlı olan bir karmaşıklık sınıfıdır (kümesidir, set)

Bu kümenin özelliği, bu kümenin üyesi olan, fonksiyon, denklem veya algoritmaların logaritmik zamanda veya logaritmik hafıza ihtiyacı ile çalışıp çalışamayacağının veya çözülüp çözülemeyeceğinin belirlenememesidir.

Bu kümenin tanım itibariyle tersi olan L (logarithmic) kümesinde bulunan problemler, algoritmalar veya fonksiyonlar ise logaritmik zamanda veya alanda çözülebilmektedir.

Bu tanımlarda geçen “zamanda veya alanda” ibaresi ile, karmaşıklığın zaman (time complexity) veya alan (memory complexity) olabileceği ifade edilmek istenmiştir. Yani, örneğin, bir algoritmanın zamansal çalışma karmaşıklığı (time complexity) NL sınıfından olurken, hafızadaki ihtiyacı (memory complexity) farklı bir sınıfta olabilir.

Logaritmik karmaşıklık konusunda bilinmesi gereken bir diğer konu ise RL sınıfıdır. Bu sınıf, tanım itibariyle olasılığa dayalı bir yapı izler. Randomized Logarithmic kelimelerinin baş harflerinden oluşan bu sınıftaki problemler, algoritmalar veya fonksiyonlar ise olasılıksal Turing Makinesi (Probabilistic Turing Machine) tarafından kabul edilirler.

Olasılıksal Turing makinesi, tanım itibariyle, sadece doğru durumları kabul eden ama yanlış durumları belirlerken hata yapabilen makinedir. Yani bir Klasik Turing makinesinde (Turing Machine) iki sonuçtan biri çıkar:

• Kabul (Accept)
• Red (Reject)

Normal bir Turing makinesi tasarım itibariyle bu iki durumu doğru olarak döndürebilmelidir. Olasılıksal Turing makinesi ilk şart olan kabul durumlarını doğru olarak döndürürken, ikinci ihtimal olan red durumlarında hata yapabilir.

RL sınıfı işte bu tip Turing makinelerinin logaritmik zamanda veya logaritmik alanda çözülebilmesi anlamındadır.

121 views