Boole Devreleri ve Devre Karmaşıklığı
Boole devreleri, mantık kapıları ağları aracılığıyla fonksiyonları hesaplar; devre karmaşıklığı ise problemleri, onları çözmek için gereken devrelerin boyutu ve derinliği ile ölçerek hesaplamanın paralel ve donanım odaklı bir görünümünü sunmaktadır.
Tanım
Boole devresi, sabit uzunluktaki ikili girdilerin bir fonksiyonunu hesaplayan, mantık kapılarından oluşan yönlendirilmiş asiklik bir grafiktir; devre karmaşıklığı ise belirli bir Boole fonksiyonları ailesini hesaplamak için gereken minimum kapı sayısını, derinliği veya diğer yapısal kaynakları incelemektedir.
Kapsam
Bu konu, Boole devrelerini ve formüllerini, karmaşıklığın boyut ve derinlik ölçütlerini, tekdüze (uniform) ve tekdüze olmayan (non-uniform) modelleri, NC ve AC gibi düşük derinlikli sınıfları, devre alt sınırları ile karmaşıklık sınıflarının ayrılması arasındaki ilişkiyi ve kısıtlı devre aileleri için dönüm noktası niteliğindeki alt sınır sonuçlarını kapsamaktadır.
Temel sorular
- Hesaplamanın kapı ağı görünümü, sıralı makinelerden nasıl farklılaşır?
- Devre boyutu ve derinliği neyi ölçer ve zaman ile paralellik ile nasıl ilişkilidir?
- Devre alt sınırları, karmaşıklık sınıflarını ayırmak için neden bir yol olarak görülmektedir?
- Hangi alt sınırlar bilinmektedir ve daha güçlü alt sınırları engelleyen bariyerler nelerdir?
Temel kuramlar
- Tekdüze Olmama Durumu (Non-uniformity) ve P/poly Sınıfı
- Devreler, her girdi uzunluğu için farklı bir makineye izin vererek P'yi içeren tekdüze olmayan P/poly sınıfını oluşturur; bir NP-tam probleminin polinom boyutlu devrelere sahip olmadığını göstermek, P'yi NP'den ayıracak ve bu da devre alt sınırlarını motive edecektir.
- Kısıtlı Devreler İçin Alt Sınırlar
- Sınırlı aileler için güçlü alt sınırlar bilinmektedir; örneğin, pariteyi hesaplayan sabit derinlikli devreler için gereken üstel boyut gibi. Ancak genel devreler için alt sınırlar hala ulaşılamaz durumdadır.
Klinik önem
Devreler, dijital donanımın doğal modelidir; bu nedenle devre karmaşıklığı, çip tasarımını ve paralel hesaplamanın sınırlarını bilgilendirmektedir. Düşük derinlikli sınıflar, birçok işlemciyle hızlı bir şekilde nelerin hesaplanabileceğini yakalamakta ve devre alt sınırları, P ile NP gibi soruları çözmeye yönelik uzun vadeli çabalarda temel bir strateji olarak öne çıkmaktadır.
Tarihçe
Shannon, 1937'de Boole cebirini anahtarlama devreleriyle ilişkilendirmiştir. Devre karmaşıklığı, 1980'lerde Furst, Saxe, Sipser ve diğerlerinin parite için sabit derinlikli alt sınırlar kanıtlamasıyla ve Razborov ile Smolensky'nin cebirsel yöntemler geliştirmesiyle bir disiplin olarak olgunlaşmıştır. Daha sonra doğal kanıtlar engeli, genel alt sınırların neden bu kadar zor elde edildiğini ortaya koymuştur.
Öne çıkan isimler
- Claude Shannon
- Alexander Razborov
- Andrew Yao
- Roman Smolensky
İlgili konular
Temel eserler
- aroraBarak2009
- vollmer1999
Sıkça sorulan sorular
- Devreler, Turing makinelerinden nasıl farklılaşır?
- Bir Turing makinesi, tüm boyutlardaki girdileri adım adım işleyen tek bir cihazken, bir devre tek bir girdi uzunluğu için sabit bir kapı ağıdır ve her uzunluk için ayrı bir devre bulunur. Bu tekdüze olmama durumu, devreleri donanımın ve paralel hesaplamanın doğal bir modeli haline getirir ve hiçbir tekdüze makinenin yapamayacağı şeyleri ifade edebilir.
- Araştırmacılar neden devre alt sınırlarını önemsemektedir?
- NP'deki bir problemin çok büyük devreler gerektirdiğini kanıtlamak, karmaşıklık sınıflarını ayıracak ve P ile NP sorununu çözebilecektir. Kısıtlı devre aileleri için alt sınırlar bilinmektedir, ancak bunları genel devrelere genişletmek resmi engellerle bloke edilmektedir; bu da alanı en derin açık zorluklarından biri haline getirmektedir.