Eşlik işlevi - Parity function

İçinde Boole cebri, bir eşlik işlevi bir Boole işlevi kimin değeri 1 ancak ve ancak giriş vektörü tek sayıda bire sahiptir. İki girişin eşlik işlevi aynı zamanda ÖZELVEYA işlevi.

Parite işlevi, teorik araştırmadaki rolü nedeniyle dikkate değerdir. devre karmaşıklığı Boole işlevlerinin.

Eşlik Fonksiyonunun çıktısı, Eşlik biti.

Tanım

${ displaystyle n}$ -variable parite işlevi Boole işlevi ${ displaystyle f: {0,1 } ^ {n} - {0,1 }}$ özelliği ile ${ displaystyle f (x) = 1}$ ancak ve ancak vektördeki birlerin sayısı ${ displaystyle x in {0,1 } ^ {n}}$ tuhaf. başka bir deyişle, ${ displaystyle f}$ aşağıdaki gibi tanımlanır:

{ displaystyle f (x) = x_ {1} oplus x_ {2} oplus dots oplus x_ {n}}

nerede ${ displaystyle oplus}$ gösterir özel veya.

Özellikleri

Parite yalnızca birlerin sayısına bağlıdır ve bu nedenle simetrik Boole işlevi.

n-variable parite işlevi ve onun olumsuzlaması, tümü için tek Boole işlevleridir. ayrık normal formlar maksimum 2 sayısına sahip^n − 1 tek terimli uzunluk n ve tüm konjonktif normal formlar maksimum 2 sayısına sahip^n − 1 uzunluk cümleleri n.^[1]

Hesaplama karmaşıklığı

Hesaplama karmaşıklığındaki en eski çalışmalardan bazıları 1961 Bella Subbotovskaya A'nın boyutunu gösteren Boole formülü hesaplama eşliği en az olmalıdır ${ displaystyle O (n ^ {3/2})}$ . Bu çalışma, rastgele kısıtlama yöntemini kullanır. Bu üs ${ displaystyle 3/2}$ dikkatli analiz yoluyla artırılmıştır. ${ displaystyle 1.63}$ tarafından Paterson ve Zwick (1993) ve sonra ${ displaystyle 2}$ tarafından Håstad (1998). ^[2]

1980'lerin başında, Merrick Furst, James Saxe ve Michael Sipser^[3] ve bağımsız olarak Miklós Ajtai^[4] kurulmuş süper polinom alt sınırlar sabit derinlik boyutunda Boole devreleri parite fonksiyonu için, yani polinom boyutlu sabit derinlikli devrelerin parite fonksiyonunu hesaplayamadığını gösterdiler. Parite işlevinden indirgeme yoluyla çoğunluk, çarpma ve geçişli kapatma işlevleri için de benzer sonuçlar elde edilmiştir.^[3]

Håstad (1987) sabit derinlik boyutunda sıkı üstel alt sınırlar oluşturdu Boole devreleri eşlik işlevi için. Håstad'ın Anahtarlama Lemması bu alt sınırlar için kullanılan temel teknik araçtır ve Johan Håstad ödüllendirildi Gödel Ödülü 1994'teki bu çalışma için. Kesin sonuç şu derinlik ... $k$ AND, OR ve NOT kapılarına sahip devreler boyut gerektirir ${ displaystyle exp ( Omega (n ^ { frac {1} {k-1}}))}$ parite fonksiyonunu hesaplamak için. derinlik olduğu için bu asimptotik olarak neredeyse optimaldir. $k$ boyuta sahip olan hesaplama paritesi devreleri ${ displaystyle exp (O (n ^ { frac {1} {k-1}}) t)}$ .

Sonsuz sürüm

Sonsuz bir eşlik işlevi bir işlevdir ${ displaystyle f iki nokta üst üste {0,1 } ^ { omega} ila {0,1 }}$ aşağıdaki özelliğe sahip her sonsuz ikili dizeyi 0 veya 1 ile eşleme: if ${ displaystyle w}$ ve ${ displaystyle v}$ Sonlu sayıda koordinatta farklılık gösteren sonsuz ikili dizelerdir ${ displaystyle f (w) = f (v)}$ ancak ve ancak ${ displaystyle w}$ ve ${ displaystyle v}$ çift koordinat sayısına göre farklılık gösterir.

Varsayım seçim aksiyomu eşlik fonksiyonlarının var olduğu ve olduğu kolayca kanıtlanabilir ${ displaystyle 2 ^ { mathfrak {c}}}$ birçoğu - tüm işlevlerin sayısı kadar ${ displaystyle {0,1 } ^ { omega}}$ -e ${ displaystyle {0,1 }}$ . Eşdeğerlik ilişki sınıfı başına bir temsilci almak yeterlidir ${ displaystyle yaklaşık}$ aşağıdaki gibi tanımlanmıştır: ${ displaystyle w yaklaşık v}$ Eğer ${ displaystyle w}$ ve ${ displaystyle v}$ sonlu koordinatlarda farklılık gösterir. Bu tür temsilcilerle hepsini 0 ile eşleştirebiliriz; geri kalanı ${ displaystyle f}$ değerler açık bir şekilde çıkarılır.

Sonsuz eşlik fonksiyonları, basit tanımları ve diğer yandan tanımlayıcı karmaşıklıkları nedeniyle genellikle teorik Bilgisayar Bilimi ve Küme Teorisinde kullanılır. Örneğin, ters bir görüntünün ${ displaystyle f ^ {- 1} [0]}$ bir Borel olmayan küme.

Ayrıca bakınız

İlgili konular

İşlevin çıktısı

Eşlik biti

Referanslar

^ Ingo Wegener Randall J. Pruim, Karmaşıklık Teorisi, 2005, ISBN 3-540-21045-8, s. 260
^ Jukna, Stasys (6 Ocak 2012). Boole Fonksiyonu Karmaşıklığı: Gelişmeler ve Sınırlar. Springer Science & Business Media. s. 167–173. ISBN 978-3642245084.
^ ^a ^b Merrick Furst, James Saxe ve Michael Sipser, "Parite, Devreler ve Polinom Zaman Hiyerarşisi", Annu. Intl. Symp. Bulunan Bilgisayar Bilimi., 1981, Hesaplama Sistemleri Teorisi, cilt. 17, hayır. 1, 1984, s. 13–27, doi:10.1007 / BF01744431
^ Miklós Ajtai, " ${ displaystyle Sigma _ {1} ^ {1}}$ -Sonlu Yapılar Üzerine Formüller ", Saf ve Uygulamalı Mantığın Yıllıkları, 24 (1983) 1–48.

Håstad, Johan (1987), Küçük derinlik devrelerinin hesaplama sınırlamaları (PDF), Ph.D. tezi, Massachusetts Institute of Technology.CS1 bakimi: ref = harv (bağlantı)

[wp-1] Ingo Wegener Randall J. Pruim, Karmaşıklık Teorisi, 2005, ISBN 3-540-21045-8, s. 260

[jukna-2] Jukna, Stasys (6 Ocak 2012). Boole Fonksiyonu Karmaşıklığı: Gelişmeler ve Sınırlar. Springer Science & Business Media. s. 167–173. ISBN 978-3642245084.

[FSS-3] Merrick Furst, James Saxe ve Michael Sipser, "Parite, Devreler ve Polinom Zaman Hiyerarşisi", Annu. Intl. Symp. Bulunan Bilgisayar Bilimi., 1981, Hesaplama Sistemleri Teorisi, cilt. 17, hayır. 1, 1984, s. 13–27, doi:10.1007 / BF01744431

[4] Miklós Ajtai, " ${ displaystyle Sigma _ {1} ^ {1}}$ -Sonlu Yapılar Üzerine Formüller ", Saf ve Uygulamalı Mantığın Yıllıkları, 24 (1983) 1–48.

[1]

[2]

[3]

[4]