Devre karmaşıklığı - Circuit complexity

Olarak teorik bilgisayar biliminin , devre karmaşıklığını dalıdır hesaplama karmaşıklığı teorisi olan Boole fonksiyonları boyutu veya derinliğine göre sınıflandırılır Boole devreler olarak hesaplamak. Bununla ilgili bir nosyon bir devre karmaşıklığı olan özyinelemeli dili olan karar bir tarafından tek tip devrelerin ailesi (aşağıya bakınız). ${\displaystyle C_{1},C_{2},\ldots }$

Açık Boolean fonksiyonlarını hesaplayan Boolean devrelerinin boyutuna ilişkin alt sınırları kanıtlamak, karmaşıklık sınıflarını ayırmak için popüler bir yaklaşımdır. Örneğin, önde gelen bir devre sınıfı P/poli , polinom boyutlu devreler tarafından hesaplanabilen Boole fonksiyonlarından oluşur. Kanıtlanması ayırmak istiyorum P ve NP (aşağıya bakınız). ${\displaystyle {\mathsf {NP}}\değil \subseteq {\mathsf {P/poli}}}$

Boolean devreleri cinsinden tanımlanan karmaşıklık sınıfları arasında AC ⁰ , AC , TC ⁰ , NC ¹ , NC ve P/poly bulunur .

Boyut ve derinlik

Giriş bitlerine sahip bir Boolean devresi, her düğümün ( bu bağlamda genellikle geçitler olarak adlandırılır ) ya giriş bitlerinden biri, bir AND geçidi , bir OR geçidi veya giriş bitlerinden biri tarafından etiketlenen 0 derecelik bir giriş düğümü olduğu, yönlendirilmiş bir döngüsel olmayan grafiktir . bir DEĞİL kapısı . Bu kapılardan biri çıkış kapısı olarak belirlenmiştir. Böyle bir devre doğal olarak girdilerinin bir fonksiyonunu hesaplar . Bir devrenin boyutu, içerdiği kapı sayısıdır ve derinliği, bir giriş kapısından çıkış kapısına giden yolun maksimum uzunluğudur. ${\görüntüleme stili n}$${\görüntüleme stili n}$${\görüntüleme stili n}$

Devre karmaşıklığının iki ana kavramı vardır . Bir Boole fonksiyonunun devre boyutu karmaşıklığı , herhangi bir devre hesaplamasının minimum boyutudur . Devre derinliği karmaşıklığı bir Boole fonksiyonunun herhangi bir devre bilgisayar az derinliğidir . ${\görüntüleme stili f}$${\görüntüleme stili f}$${\görüntüleme stili f}$${\görüntüleme stili f}$

Bu kavramlar, özellikle sonsuz biçimsel diller olmak üzere, farklı bit uzunluklarına sahip diziler içeren herhangi bir dilin devre karmaşıklığı göz önüne alındığında genelleşir . Ancak Boolean devreleri yalnızca sabit sayıda giriş bitine izin verir. Bu nedenle, tek bir Boolean devresi böyle bir dile karar veremez. Bu olasılığı hesaba katmak için, her birinin boyut girişlerini kabul ettiği devre aileleri göz önünde bulundurulur . Her devre ailesi, bir uzunluk dizesi ailenin bir üyesi olduğunda ve aksi halde devre çıkışı vererek dili doğal olarak üretecektir . Herhangi bir boyuttaki girdilere karar veren başka bir aile yoksa (sırasıyla derinlik minimum aileleri için) daha küçük boyutlu bir devre ile bir devre ailesinin boyutu minimumdur diyoruz . Böylece devre karmaşıklığı özyinelemeli olmayan diller için bile anlamlıdır . Tek tip bir aile kavramı, devre karmaşıklığının varyantlarının, özyinelemeli dillerin algoritma tabanlı karmaşıklık ölçümleriyle ilişkilendirilmesini sağlar. Bununla birlikte, tek biçimli olmayan varyant, belirli dillere karar vermek için herhangi bir devre ailesinin ne kadar karmaşık olması gerektiğine dair alt sınırlar bulmaya yardımcı olur. ${\displaystyle C_{1},C_{2},\ldots }$${\ Displaystyle C_{n}}$${\görüntüleme stili n}$${\ Displaystyle C_{n}}$${\görüntüleme stili 1}$${\görüntüleme stili n}$${\görüntüleme stili 0}$${\görüntüleme stili n}$${\ Displaystyle C_{n}}$

Bu nedenle, biçimsel bir dilin devre boyutu karmaşıklığı , bir girdinin bit uzunluğunu , o uzunluktaki girdilerin içinde olup olmadığına karar veren bir minimal devrenin devre boyutu karmaşıklığıyla ilişkilendiren fonksiyon olarak tanımlanır . Devre derinlik karmaşıklığı benzer bir şekilde tanımlanır. ${\görüntüleme stili A}$${\displaystyle t:\mathbb {N} \to \mathbb {N} }$${\görüntüleme stili n}$${\ Displaystyle C_{n}}$${\görüntüleme stili A}$

tekdüzelik

Boolean devreleri , aynı hesaplama cihazının tümü için kullanıldığı Turing makineleri gibi tek tip modellerin aksine, farklı uzunluklardaki girdilerin farklı devreler tarafından işlenmesi anlamında tekdüze olmayan hesaplama modellerinin başlıca örneklerinden biridir. olası giriş uzunlukları Bireysel bir hesaplama problemi bu nedenle , her birinin n bitlik devre işleme girdileri olduğu belirli bir Boolean devreleri ailesi ile ilişkilidir . Bu ailelere genellikle , n girişinde bireysel devrenin bir tanımını üreten , muhtemelen kaynakla sınırlı bir Turing makinesinin varlığını gerektiren bir tekdüzelik koşulu uygulanır . Bu Turing makinesi n cinsinden bir çalışma süresi polinomuna sahip olduğunda, devre ailesinin P-düzgün olduğu söylenir. DLOGTIME -uniformity'nin daha katı gereksinimi, AC ⁰ veya TC ⁰ gibi sığ-derinlik devre sınıflarının incelenmesinde özellikle ilgi çekicidir . Hiçbir kaynak sınırı belirtilmediğinde, bir dil özyinelemelidir (yani, bir Turing makinesi tarafından karar verilebilir), ancak ve ancak dile tek tip bir Boolean devreleri ailesi tarafından karar verilirse. ${\displaystyle C_{1},C_{2},\dots }$${\ Displaystyle C_{n}}$${\ Displaystyle C_{n}}$

Polinom zamanlı üniforma

Bir Boolean devreleri ailesi, deterministik bir Turing makinesi M varsa , polinom-zaman üniformudur , öyle ki ${\displaystyle \{C_{n}:n\in \mathbb {N} \}}$

• M polinom zamanında çalışır
• Tüm için , M bir açıklama çıktılar girişine${\displaystyle n\in \mathbb {N} }$${\ Displaystyle C_{n}}$${\görüntüleme stili 1^{n}}$

Günlük alanı üniforması

Bir Boolean devreleri ailesi, deterministik bir Turing makinesi M varsa , logspace tekdüzedir , öyle ki ${\displaystyle \{C_{n}:n\in \mathbb {N} \}}$

• M logaritmik uzayda çalışır
• Tüm için , M bir açıklama çıktılar girişine${\displaystyle n\in \mathbb {N} }$${\ Displaystyle C_{n}}$${\görüntüleme stili 1^{n}}$

Tarih

Devre karmaşıklığı , n değişken üzerindeki neredeyse tüm Boole fonksiyonlarının Θ(2 ⁿ / n ) boyutunda devreler gerektirdiğini kanıtlayan 1949'da Shannon'a kadar gider . Bu gerçeğe rağmen, karmaşıklık teorisyenleri, hesaplanması zor olması amacıyla açıkça oluşturulmuş fonksiyonlar üzerinde yalnızca süperpolinom devresinin alt sınırlarını kanıtlayabilmişlerdir .

Daha yaygın olarak, süperpolinom alt sınırları, kullanılan devre ailesi üzerinde belirli kısıtlamalar altında kanıtlanmıştır. Süperpolinom devresinin alt sınırlarının gösterildiği ilk fonksiyon , modülo 2 girdi bitlerinin toplamını hesaplayan parite fonksiyonuydu . Paritenin AC ^0'da yer almadığı gerçeği ilk olarak 1983'te Ajtai ve Furst, Saxe tarafından bağımsız olarak belirlendi. ve 1984'te Sipser. 1987'de Håstad tarafından yapılan sonraki iyileştirmeler , parite fonksiyonunu hesaplayan herhangi bir sabit derinlikli devre ailesinin üstel boyut gerektirdiğini ortaya koydu. Razborov'un bir sonucunu genişleterek, 1987'de Smolensky, devre, giriş bitlerinin toplamını modülo bazı tek asal p'yi hesaplayan kapılarla artırılsa bile bunun doğru olduğunu kanıtladı .

K -clique sorun ile ilgili belirli bir grafiktir karar için n tane köşe boyutu bir klik sahip k . n ve k sabitlerinin herhangi bir özel seçimi için , grafik, her olası kenar için mevcut olup olmadığını gösteren bitler kullanılarak ikili olarak kodlanabilir . Daha sonra k -clique sorunu, ancak ve ancak dizge tarafından kodlanan grafiğin k boyutunda bir klik içermesi durumunda 1 çıktısını veren bir fonksiyon olarak resmileştirilir . Bu fonksiyon ailesi monotondur ve bir devre ailesi tarafından hesaplanabilir, ancak polinom boyutlu monoton devreler ailesi tarafından hesaplanamayacağı gösterilmiştir (yani, VE ve VEYA geçitleri olan ancak olumsuzlama olmayan devreler). Razborov'un 1985'teki orijinal sonucu daha sonra 1987'de Alon ve Boppana tarafından üstel boyutlu bir alt sınıra geliştirildi. 2008'de Rossman VE, VEYA ve DEĞİL kapılı sabit derinlikli devrelerin k- kliğini çözmek için boyut gerektirdiğini gösterdi. ortalama durumda bile sorun . Ayrıca, hesaplayan bir boyut devresi var . ${\displaystyle {n \2'yi seçin}}$${\displaystyle f_{k}:\{0,1\}^{n \seçin 2}\to \{0,1\}}$${\displaystyle f_{k}}$${\görüntüleme stili \Omega (n^{k/4})}$${\ Displaystyle n^{k/4+O(1)}}$${\displaystyle f_{k}}$

1999'da Raz ve McKenzie daha sonra monoton NC hiyerarşisinin sonsuz olduğunu gösterdi.

Tamsayı Bölme Problemi, tek tip TC ^0'da yatmaktadır .

Devre alt sınırları

Devre alt sınırları genellikle zordur. Bilinen sonuçlar şunları içerir:

• Parite, 1983'te Ajtai ve 1984'te Furst, Saxe ve Sipser tarafından kanıtlanan AC ⁰ düzgün olmayan bir yapıda değildir.
• Üniforma TC ⁰ kesinlikle bulunan PP Allender'a tarafından kanıtlanmıştır.
• S sınıfları^P
  ₂, PP ve MA /1 (bir bit tavsiye ile MA ) herhangi bir k sabiti için SIZE ( n ^k ) içinde değildir .
• Tek biçimli olmayan ACC ⁰ sınıfının çoğunluk işlevini içermediğinden şüphelenilse de, Williams bunu ancak 2010'da kanıtladı .${\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}}$

NEXPTIME'ın düzgün olmayan TC ⁰ devrelerine sahip olup olmadığı açıktır .

Devre alt sınırlarının kanıtları derandomizasyona güçlü bir şekilde bağlıdır . Polinom boyutu ve polinom derecesinin tek biçimli olmayan aritmetik devreleriyle (polinomlar) hesaplanamayacağını ya da kalıcı olduğunu ima edecek bir kanıt . ${\displaystyle {\mathsf {P}}={\mathsf {BPP}}}$${\displaystyle {\mathsf {NEXP}}\değil \subseteq {\mathsf {P/poli}}}$

1997'de Razborov ve Rudich, açık Boole fonksiyonları için bilinen birçok devre alt sınırının , ilgili devre sınıfına karşı yararlı olan sözde doğal özelliklerin varlığını ima ettiğini gösterdi . Öte yandan, P/poly'ye karşı yararlı olan doğal özellikler, güçlü sözde rasgele üreteçleri bozar. Bu genellikle, güçlü devre alt sınırlarını kanıtlamak için "doğal kanıtlar" engeli olarak yorumlanır. 2016 yılında Carmosino, Impagliazzo, Kabanets ve Kolokolova, doğal özelliklerin verimli öğrenme algoritmaları oluşturmak için de kullanılabileceğini kanıtladı.

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

Birçok devre karmaşıklığı sınıfı, sınıf hiyerarşileri açısından tanımlanır. Negatif olmayan her i tamsayı için , sınırlı fan-in AND, OR ve NOT geçitlerini kullanan polinom boyutlu derinlik devrelerinden oluşan bir NC ⁱ sınıfı vardır . Tüm bu sınıfların NC birliği tartışmaya açıktır. Sınırsız fan giriş kapıları dikkate alınarak, AC ⁱ ve AC (NC'ye eşittir) sınıfları oluşturulabilir. Aynı boyut ve derinlik kısıtlamalarına sahip diğer birçok devre karmaşıklığı sınıfı, farklı kapı kümelerine izin verilerek oluşturulabilir. ${\displaystyle O(\log ^{i}(n))}$

Zaman karmaşıklığı ile ilişkisi

Belirli bir dili, varsa aittir zaman karmaşıklığı sınıfının bazı fonksiyon için , daha sonra devre karmaşıklığı vardır . ${\görüntüleme stili A}$ ${\görüntüleme stili {\metin{ZAMAN}}(t(n))}$${\displaystyle t:\mathbb {N} \to \mathbb {N} }$${\görüntüleme stili A}$${\displaystyle {\mathcal {O}}(t^{2}(n))}$

Ayrıca bakınız

• Devre minimizasyonu

Notlar

Referanslar

daha fazla okuma

• Vollmer, Heribert (1999). Devre Karmaşıklığına Giriş: Tekdüzen Bir Yaklaşım . Teorik Bilgisayar Bilimlerinde Metinler. Bir EATCS Serisi. Springer Verlag'ın fotoğrafı . ISBN'si 978-3-540-64310-4.
• Wegener, Ingo (1987) [Kasım 1986]. Boole Fonksiyonlarının Karmaşıklığı . Bilgisayar Bilimlerinde Wiley-Teubner Serisi. Frankfurt am Main/Bielefeld, Almanya: John Wiley & Sons Ltd. ve BG Teubner Verlag , Stuttgart. ISBN'si 3-519-02107-2. LCCN  87-10388 .(xii + 457 sayfa) (NB. zamanında konuda etkili bir ders kitabı, yaygın. "Mavi Kitap" olarak bilinen olarak da alınabilir anda indirmek (PDF) de Hesaplamalı Karmaşıklık Elektronik Kolokyumu .)
• Zwick, Uri . "Devre karmaşıklığı üzerine Uri Zwick kursu için ders notları" .