L (karmaşıklık) - L (complexity)

Olarak hesaplama karmaşıklığı teori , L (aynı zamanda LSPACE veya DLOGSPACE ) olan karmaşıklığı sınıfı içeren karar problemlerini bir çözülebilir deterministik Turing makinesi , bir ile logaritmik yazılabilir miktarını bellek alanı . Resmi olarak, Turing makinesinin biri girişi kodlayan ve yalnızca okunabilen iki teybi vardır, diğer teyp ise logaritmik boyuta sahiptir ancak yazıldığı kadar okunabilir de. Logaritmik alan, girdiye sabit sayıda işaretçi ve logaritmik sayıda boole bayrağı tutmak için yeterlidir ve birçok temel logspace algoritması belleği bu şekilde kullanır.

Komple problemler ve mantıksal karakterizasyon

Her önemsiz olmayan sorun L olan tam altında log-uzay indirimleri , böylece daha zayıf azalmalar anlamlı kavramlarını tanımlamak için gerekli olan L -completeness en yaygın olan birinci dereceden indirimleri .

Tarafından 2004 yılında sonuç Ömer Reingold gösteren USTCON , belirli bir iki köşe arasında bir yol vardır var olup olmadığına dair bir sorun yönsüz grafikte , içinde L gösteren, L = SL USTCON olduğu, SL -Komple.

Bunun bir sonucu, L'nin basit bir mantıksal karakterizasyonudur : tam olarak birinci dereceden mantıkta eklenmiş bir değişmeli geçişli kapatma operatörüyle ifade edilebilen dilleri içerir ( grafik teorik terimlerinde bu, her bağlı bileşeni bir kliğe dönüştürür ). Bu sonucun veritabanı sorgu dilleri için uygulaması vardır : bir sorgunun veri karmaşıklığı , değişken girdi olarak veri boyutunu dikkate alarak sabit bir sorguyu yanıtlamanın karmaşıklığı olarak tanımlanır. Bu tedbir için, karşı sorulara ilişkisel veri tabanları tam bilgi (bir bağı sahip boş değerlere örneğin ifade edilen) ilişkisel cebir olan L .

İlgili karmaşıklık sınıfları

L bir alt sınıfıdır NL içinde Karar verilebilen dil sınıfıdır, logaritmik bir boş alan nondeterministic Turing makinası . Bir sorun, NL bir sorun haline transforme edilebilir erişilebilirlik bir de ilgilidir grafik durumları ve deterministik olmayan makinenin durum geçişlerini temsil ve bağlanan logaritmik alan bu grafik, izler olan köşe ve kenarlar bir polinom sayıda sahip olduğunu ima eder NL deterministik polinom zamanında çözülebilen problemlerin karmaşıklık sınıfı P'de bulunur. Böylece L  ⊆  NL  ⊆  P . Dahil L içine P da daha doğrudan ispat edilebilir: Bir kullanarak decider O (log  n, 2'den fazla kullanamaz) alan O (log  n )  =  n- O (1) zaman, bu mümkün konfigürasyonlar sayısı olduğu için.

L ayrıca NC sınıfıyla şu şekilde ilişkilidir : NC 1  ⊆  L  ⊆  NL  ⊆  NC 2 . Bir deyişle, bir paralel bilgisayar verilen C bir polinom sayısı ile O ( n, k bir sabit için işlemcilerin) k , çözülebilecek herhangi bir sorun C de O (giriş  n ) zaman içinde , L , ve herhangi bir sorun, L olabilir C'de O (log 2  n ) zamanında çözüldü .

Önemli açık problemler , L  =  P olup olmadığını ve L  =  NL olup olmadığını içerir . L  =  NP olup olmadığı bile bilinmiyor .

İlgili sınıf işlevi sorunlarına olan FL . FL , genellikle günlük alanı azaltmalarını tanımlamak için kullanılır .

Ek özellikler

L ise düşük , her bir sorgu için aynı alan yeniden giriş alanı, (yaklaşık olarak, "kullanım günlük alan fonksiyon aramalar" konuşma) log-alan torpil sorgular simüle, çünkü kendisi için.

Diğer kullanımlar

Logspace'in ana fikri, logspace'de bir polinom büyüklüğündeki sayının saklanabilmesi ve bunu girdinin bir pozisyonuna işaretçileri hatırlamak için kullanabilmesidir.

Bu nedenle logspace sınıfı, girdinin bir bilgisayarın RAM'ine sığmayacak kadar büyük olduğu hesaplamaları modellemek için kullanışlıdır . Uzun DNA dizileri ve veritabanları, belirli bir zamanda girdinin yalnızca sabit bir bölümünün RAM'de olacağı ve denetlenecek girdinin bir sonraki bölümünü hesaplamak için işaretçilere sahip olduğumuz, böylece yalnızca logaritmik bellek kullandığımız sorunlara iyi örneklerdir.

Ayrıca bakınız

Notlar

Referanslar