Paritetsfunktion

I boolesk algebra är en paritetsfunktion en boolesk funktion vars värde är ett om och endast om ingångsvektorn har ett udda antal ettor. Paritetsfunktionen för två ingångar är också känd som XOR -funktionen.

Paritetsfunktionen är anmärkningsvärd för sin roll i teoretisk undersökning av kretskomplexiteten för booleska funktioner.

Utdata från paritetsfunktionen är paritetsbiten .

Definition

Funktionen $n$ -variabel paritet är den booleska funktionen $f:\{0,1\}^{n}\to \{0,1 \}$ med egenskapen att $f(x)=1$ om och endast om antalet ettor i vektorn $x\in \{0 ,1\}^{n}$ är udda. Med andra ord, $f$ definieras enligt följande:

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

där $\oplus$ anger exklusiv eller .

Egenskaper

Paritet beror bara på antalet ettor och är därför en symmetrisk boolesk funktion .

Den n -variable paritetsfunktionen och dess negation är de enda booleska funktionerna för vilka alla disjunktiva normalformer har det maximala antalet 2 ^{n − 1} monomer med längden n och alla konjunktiva normalformer har det maximala antalet 2 ^{n − 1} längdsatser n .

Beräkningskomplexitet

Något av det tidigaste arbetet inom beräkningskomplexitet var 1961 bundet av Bella Subbotovskaya, vilket visar storleken på en boolesk formel som beräkningsparitet måste vara minst $O(n^{3/2})$ . Detta arbete använder metoden med slumpmässiga begränsningar. Denna exponent av $3/2$ har ökats genom noggrann analys till $1,63$ Paterson och Zwick ( 1993) och sedan till $displaystyle 2}$ av Håstad (1998).

I början av 1980-talet etablerade Merrick Furst, James Saxe och Michael Sipser och oberoende Miklós Ajtai superpolynomiska nedre gränser för storleken på booleska kretsar med konstant djup för paritetsfunktionen, dvs de visade att kretsar med konstant djup av polynomstorlek inte kan beräkna paritetsfunktionen. Liknande resultat fastställdes också för majoritet, multiplikation och transitiva stängningsfunktioner, genom reduktion från paritetsfunktionen.

Håstad (1987) fastställde snäva exponentiella nedre gränser för storleken på booleska kretsar med konstant djup för paritetsfunktionen. Håstads Switching Lemma är det nyckeltekniska verktyget som används för dessa nedre gränser och Johan Håstad tilldelades Gödelpriset för detta arbete 1994. Det exakta resultatet är att djupkretsar $med$ AND-, OR- och NOT-grindar kräver storlek $\exp(\Omega (n^{\frac {1}{k-1}}))$ för att beräkna paritetsfunktionen. Detta är asymptotiskt nästan optimalt eftersom det finns djup- $k$ -kretsar som beräknar paritet som har storleken $\exp(O(n^{\frac {1}{k-1 }})t)$ .

Oändlig version

En oändlig paritetsfunktion är en funktion ${\displaystyle f\colon \{0,1\}^{\omega }\to \{0,1\}} som$ avbildar varje oändlig binär sträng till 0 eller 1, med följande egenskap: om $w$ och $v$ är oändliga binära strängar som endast skiljer sig åt på ändligt antal koordinater, då $f(w)=f(v)$ om och endast om $w$ och $v$ skiljer sig åt på jämna antal koordinater.

Om man antar valets axiom kan det enkelt bevisas att paritetsfunktioner existerar och att det finns $2^{\mathfrak {c}}$ många av dem - lika många som antalet av alla funktioner från $\{0,1\}^{\omega }$ till $\{0,1\}$ . Det räcker att ta en representant per ekvivalensklass av relation $\approx$ definierad enligt följande: $w\approx v$ om $w$ och $v$ skiljer sig åt vid ändligt antal koordinater. Med sådana representanter kan vi mappa dem alla till 0; resten av $f$ -värdena dras av entydigt.

Oändliga paritetsfunktioner används ofta i teoretisk datavetenskap och mängdteori på grund av deras enkla definition och - å andra sidan - deras beskrivande komplexitet. Till exempel kan det visas att en invers bild $f^{-1}[0]$ är en icke-Borel-mängd .

Se även

Walsh-funktion , en kontinuerlig motsvarighet
Paritetsbit , utgången av funktionen
Piling-up lemma , en statistisk egenskap för oberoende indata
Flervägsväxling , en fysisk implementering som ofta används för att styra belysning

Relaterade ämnen:

Håstad, Johan (1987), Beräkningsbegränsningar av små djupkretsar (PDF) , Ph.D. avhandling, Massachusetts Institute of Technology.