Boole devresi - Boolean circuit

Örnek Boole devresi.

{displaystyle wedge}

düğümler AND kapıları,

{displaystyle vee}

düğümler OR kapıları, ve

{displaystyle eg}

düğümler KAPILAR DEĞİL

İçinde hesaplama karmaşıklığı teorisi ve devre karmaşıklığı, bir Boole devresi matematikseldir model kombinasyonel için dijital mantık devreleri. Bir resmi dil olası her giriş uzunluğu için bir devre olan bir Boole devreleri ailesi tarafından kararlaştırılabilir. Boole devreleri aynı zamanda resmi bir model olarak kullanılır. kombinasyonel mantık dijital elektronikte.

Boole devreleri, mantık kapıları içerdikleri. Örneğin, bir devre şunları içerebilir: ikili VE ve VEYA kapıları ve birli Kapı DEĞİL veya tamamen ikili olarak tanımlanmamalıdır NAND kapıları. Her kapı bazılarına karşılık gelir Boole işlevi sabit sayıda alan bitler giriş ve çıkış olarak tek bir bit.

Boole devreleri, kullanılan birçok dijital bileşen için bir model sağlar. bilgisayar Mühendisliği, dahil olmak üzere çoklayıcılar, toplayıcılar, ve aritmetik mantık birimleri ama hariç tutuyorlar sıralı mantık. Bunlar, gerçek dijital mantık devrelerinin tasarlanmasıyla ilgili birçok yönü göz ardı eden bir soyutlamadır. metastabilite, yayılma, aksaklıklar, güç tüketimi, ve yayılma gecikmesi değişkenlik.

Resmi tanımlama

Boole devrelerinin resmi bir tanımını verirken, Vollmer bir temeli küme olarak tanımlayarak başlar B Boole işlevlerinin, devre modelinde izin verilen kapılara karşılık gelir. Temel üzerinde bir Boole devresi B, ile n girişler ve m çıktılar, daha sonra sonlu olarak tanımlanır Yönlendirilmiş döngüsüz grafiği. Her köşe, bir temel işleve veya girdilerden birine karşılık gelir ve bir tam m çıktılar olarak etiketlenen düğümler.^[1] Aynı Boole işlevine yönelik farklı argümanlar arasında ayrım yapmak için kenarların da bir sıralaması olmalıdır.^[2]

Özel bir durum olarak önerme formülü veya Boole ifadesi diğer her düğümün sahip olduğu tek bir çıkış düğümüne sahip bir Boole devresidir. yayılma 1. Dolayısıyla, bir Boole devresi, paylaşılan alt formüller ve çoklu çıkışlara izin veren bir genelleme olarak kabul edilebilir.

Boole devreleri için ortak bir temel, {VE, VEYA, DEĞİL }, hangisi işlevsel olarak tamamlandı, ben. e. diğer tüm Boole işlevlerinin oluşturulabileceği.

Hesaplama karmaşıklığı

Arka fon

Belirli bir devre yalnızca sabit boyuttaki girişlere etki eder. Ancak, resmi diller ( dizeye dayalı temsilleri karar problemleri ) farklı uzunluklarda dizeler içerir, bu nedenle diller tek bir devre tarafından tam olarak yakalanamaz (bir dilin tek bir Turing makinesi tarafından tam olarak tanımlandığı Turing makine modelinin aksine). Bir dil bunun yerine bir devre ailesi. Bir devre ailesi sonsuz bir devre listesidir ${displaystyle (C_ {0}, C_ {1}, C_ {2}, ...)}$ , nerede ${displaystyle C_ {n}}$ vardır ${displaystyle n}$ girdi değişkenleri. Bir devre ailesinin bir dile karar verdiği söylenir ${displaystyle L}$ eğer, her dizge için ${displaystyle w}$ , ${displaystyle w}$ dilde ${displaystyle L}$ ancak ve ancak ${displaystyle C_ {n} (w) = 1}$ , nerede ${displaystyle n}$ uzunluğu ${displaystyle w}$ . Başka bir deyişle, bir dil, uzunluklarına karşılık gelen devrelere uygulandığında 1 olarak değerlendirilen dizeler kümesidir.^[3]

Karmaşıklık ölçüleri

Birkaç önemli karmaşıklık ölçüleri Boole devrelerinde, devre derinliği, devre boyutu ve AND geçitleri ile OR geçitleri arasındaki alternatiflerin sayısı dahil olmak üzere tanımlanabilir. Örneğin, bir Boole devresinin boyut karmaşıklığı, kapıların sayısıdır.

Devre boyutu karmaşıklığı arasında doğal bir bağlantı olduğu ortaya çıktı. zaman karmaşıklığı.^[4] Sezgisel olarak, küçük zaman karmaşıklığına sahip bir dil (yani, bir Turing makinesi ), aynı zamanda küçük bir devre karmaşıklığına sahiptir (yani, nispeten az Boole işlemi gerektirir). Resmi olarak, eğer bir dilin ${displaystyle {mathsf {TIME}} (t (n))}$ , nerede ${displaystyle t}$ bir işlev ${displaystyle t: mathbb {N} o mathbb {N}}$ , sonra devre karmaşıklığı var ${görüntü stili O (t ^ {2} (n))}$ .

Karmaşıklık sınıfları

Boole devreleri açısından birkaç önemli karmaşıklık sınıfı tanımlanmıştır. Bunların en genel olanı P / poli, polinom boyutlu devre aileleri tarafından karar verilebilen diller kümesi. Doğrudan dillerin ${displaystyle {mathsf {TIME}} (t (n))}$ devre karmaşıklığına sahip ${görüntü stili O (t ^ {2} (n))}$ o P ${displaystyle subseteq}$ P / poli. Başka bir deyişle, deterministik bir Turing makinesi tarafından polinom zamanında hesaplanabilen herhangi bir problem, polinom boyutlu bir devre ailesi tarafından da hesaplanabilir. Dahil etmenin uygun olduğu durum da budur (yani P ${displaystyle subsetneq}$ P / poly) çünkü P / poly'de kararlaştırılamayan sorunlar vardır. P / poly, karmaşıklık sınıfları arasındaki ilişkilerin incelenmesinde onu oldukça kullanışlı kılan bir dizi özelliğe sahip olduğu ortaya çıkar. Özellikle, ilgili sorunların araştırılmasında yararlıdır. P ve NP. Örneğin, NP'de P / poly'de olmayan herhangi bir dil varsa P ${displaystyle eq}$ NP.^[5] P / poly aynı zamanda polinom hiyerarşi. Örneğin, eğer NP ⊆ P / poly, ardından PH çöker ${displaystyle Sigma _ {2} ^ {mathsf {P}}}$ . P / poly ve diğer karmaşıklık sınıfları arasındaki ilişkilerin tam açıklaması "P / poly'nin önemi ". P / poli, aynı zamanda, polinomla sınırlı bir polinom-zamanlı Turing makinesi tarafından tanınan diller sınıfı olarak da tanımlanabilecek ilginç bir özelliğe sahiptir tavsiye işlevi.

Kendi başlarına ilginç özelliklere sahip iki P / poly alt sınıfı şunlardır: NC ve AC. Bu sınıflar yalnızca devre boyutları açısından değil, aynı zamanda derinlik. Bir devrenin derinliği en uzun olanın uzunluğudur. yönlendirilmiş yol bir giriş düğümünden çıkış düğümüne. NC sınıfı, yalnızca polinom boyutuna sahip olmakla değil, aynı zamanda sahip olmakla sınırlı olan devre aileleri tarafından çözülebilen diller kümesidir. polilogaritmik derinlik. AC sınıfı, NC'ye benzer şekilde tanımlanır, ancak geçitlerin sınırsız fan girişine sahip olmasına izin verilir (yani, AND ve OR kapıları ikiden fazla bite uygulanabilir). NC önemli bir sınıftır çünkü verimli olan dil sınıfını temsil ettiği ortaya çıkmıştır. paralel algoritmalar.

Devre değerlendirmesi

Devre Değeri Problemi - verilen bir girişte belirli bir Boole devresinin çıktısını hesaplama problemi dizi - bir P-tamamlandı karar problemi.^[6] Bu nedenle, problemi çözen verimli, oldukça paralel bir algoritma bulunmaması anlamında bu problemin "doğası gereği sıralı" olduğu düşünülmektedir.

Ayrıca bakınız

Dipnotlar

^ Vollmer 1999, s. 8.
^ Vollmer 1999, s. 9.
^ Sipser, Michael (2006). Hesaplama Teorisine Giriş (2. baskı). ABD: Thomson Kurs Teknolojisi. s. 354. ISBN 978-0-534-95097-2.
^ Sipser, Michael (2006). Hesaplama Teorisine Giriş (2. baskı). ABD: Thomson Kurs Teknolojisi. s. 355. ISBN 978-0-534-95097-2.
^ Arora, Sanjeev; Barak, Boaz (2009). Hesaplamalı Karmaşıklık: Modern Bir Yaklaşım. Cambridge University Press. s. 286. ISBN 978-0-521-42426-4.
^ Arora, Sanjeev; Barak, Boaz (2009). Hesaplamalı Karmaşıklık: Modern Bir Yaklaşım. Cambridge University Press. s. 119. ISBN 978-0-521-42426-4.

Referanslar

Vollmer, Heribert (1999). Devre Karmaşıklığına Giriş. Berlin: Springer. ISBN 3-540-64310-9.

[1] Vollmer 1999, s. 8.

[2] Vollmer 1999, s. 9.

[3] Sipser, Michael (2006). Hesaplama Teorisine Giriş (2. baskı). ABD: Thomson Kurs Teknolojisi. s. 354. ISBN 978-0-534-95097-2.

[4] Sipser, Michael (2006). Hesaplama Teorisine Giriş (2. baskı). ABD: Thomson Kurs Teknolojisi. s. 355. ISBN 978-0-534-95097-2.

[arorabarak-5] Arora, Sanjeev; Barak, Boaz (2009). Hesaplamalı Karmaşıklık: Modern Bir Yaklaşım. Cambridge University Press. s. 286. ISBN 978-0-521-42426-4.

[6] Arora, Sanjeev; Barak, Boaz (2009). Hesaplamalı Karmaşıklık: Modern Bir Yaklaşım. Cambridge University Press. s. 119. ISBN 978-0-521-42426-4.

[1]

[2]

[3]

[4]

[5]

[6]