Parity function




In Boolean algebra, a parity function is a Boolean function whose value is 1 if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function.


The parity function is notable for its role in theoretical investigation of circuit complexity of Boolean functions.


The output of the Parity Function is the Parity bit.




Contents






  • 1 Definition


  • 2 Properties


  • 3 Computational complexity


  • 4 Infinite version


  • 5 See also


  • 6 References





Definition


The n{displaystyle n}n-variable parity function is the Boolean function f:{0,1}n→{0,1}{displaystyle f:{0,1}^{n}to {0,1}}f:{0,1}^{n}to {0,1} with the property that f(x)=1{displaystyle f(x)=1}f(x)=1 if and only if the number of ones in the vector x∈{0,1}n{displaystyle xin {0,1}^{n}}xin {0,1}^{n} is odd.
In other words, f{displaystyle f}f is defined as follows:



f(x)=x1⊕x2⊕⋯⊕xn{displaystyle f(x)=x_{1}oplus x_{2}oplus dots oplus x_{n}}f(x)=x_{1}oplus x_{2}oplus dots oplus x_{n}.


Properties


Parity only depends on the number of ones and is therefore a symmetric Boolean function.


The n-variable parity function and its negation are the only Boolean functions for which all disjunctive normal forms have the maximal number of 2 n − 1monomials of length n and all conjunctive normal forms have the maximal number of 2 n − 1 clauses of length n.[1]



Computational complexity


Some of the earliest work in computational complexity was 1961 bound of Bella Subbotovskaya showing the size of a Boolean formula computing parity must be at least O(n3/2){displaystyle O(n^{3/2})}{displaystyle O(n^{3/2})}. This work uses the method of random restrictions. This exponent of 3/2{displaystyle 3/2}{displaystyle 3/2} has been increased through careful analysis to 1.63{displaystyle 1.63}{displaystyle 1.63} by Paterson and Zwick (1993) and then to 2{displaystyle 2}2 by Håstad (1998). [2]


In the early 1980s, Merrick Furst, James Saxe and Michael Sipser[3] and independently Miklós Ajtai[4] established super-polynomial lower bounds on the size of constant-depth Boolean circuits for the parity function, i.e., they showed that polynomial-size constant-depth circuits cannot compute the parity function. Similar results were also established for the majority, multiplication and transitive closure functions, by reduction from the parity function.[3]


Håstad (1987) established tight exponential lower bounds on the size of constant-depth Boolean circuits for the parity function. Håstad's Switching Lemma is the key technical tool used for these lower bounds and Johan Håstad was awarded the Gödel Prize for this work in 1994.
The precise result is that depth-k circuits with AND, OR, and NOT gates require size exp⁡(Ω(n1k−1)){displaystyle exp(Omega (n^{frac {1}{k-1}}))}exp(Omega(n^{frac{1}{k-1}})) to compute the parity function.
This is asymptotically almost optimal as there are depth-k circuits computing parity which have size exp⁡(O(n1k−1)t){displaystyle exp(O(n^{frac {1}{k-1}})t)}exp(O(n^{frac{1}{k-1}})t).



Infinite version


An infinite parity function is a function f:{0,1}ω→{0,1}{displaystyle fcolon {0,1}^{omega }to {0,1}}fcolon {0,1}^{{omega }}to {0,1} mapping every infinite binary string to 0 or 1, having the following property: if w{displaystyle w}w and v{displaystyle v}v are infinite binary strings differing only on finite number of coordinates then f(w)=f(v){displaystyle f(w)=f(v)}f(w)=f(v) if and only if w{displaystyle w}w and v{displaystyle v}v differ on even number of coordinates.


Assuming axiom of choice it can be easily proved that parity functions exist and there are 2c{displaystyle 2^{mathfrak {c}}}2^{{{mathfrak {c}}}} many of them - as many as the number of all functions from {0,1}ω{displaystyle {0,1}^{omega }}{0,1}^{{omega }} to {0,1}{displaystyle {0,1}}{0,1}. It is enough to take one representative per equivalence class of relation ≈{displaystyle approx }approx defined as follows: w≈v{displaystyle wapprox v}wapprox v if w{displaystyle w}w and v{displaystyle v}v differ at finite number of coordinates. Having such representatives, we can map all of them to 0; the rest of f{displaystyle f}f values are deducted unambiguously.


Infinite parity functions are often used in theoretical Computer Science and Set Theory because of their simple definition and - on the other hand - their descriptive complexity. For example, it can be shown that an inverse image f−1[0]{displaystyle f^{-1}[0]}f^{{-1}}[0] is a non-Borel set.



See also


Related topics



  • Error Correction

  • Error Detection


The output of the function


  • Parity bit


References


.mw-parser-output .refbegin{font-size:90%;margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{list-style-type:none;margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li,.mw-parser-output .refbegin-hanging-indents>dl>dd{margin-left:0;padding-left:3.2em;text-indent:-3.2em;list-style:none}.mw-parser-output .refbegin-100{font-size:100%}




  1. ^ Ingo Wegener, Randall J. Pruim, Complexity Theory, 2005, .mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
    ISBN 3-540-21045-8, p. 260


  2. ^ Jukna, Stasys (Jan 6, 2012). Boolean Function Complexity: Advances and Frontiers. Springer Science & Business Media. pp. 167–173. ISBN 978-3642245084.


  3. ^ ab Merrick Furst, James Saxe and Michael Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Annu. Intl. Symp. Found.Coimputer Sci., 1981, Theory of Computing Systems, vol. 17, no. 1, 1984, pp. 13–27, doi:10.1007/BF01744431


  4. ^ Miklós Ajtai, "Σ11{displaystyle Sigma _{1}^{1}}Sigma _{1}^{1}-Formulae on Finite Structures", Annals of Pure and Applied Logic, 24 (1983) 1–48.




  • Håstad, Johan (1987), Computational limitations of small depth circuits (PDF), Ph.D. thesis, Massachusetts Institute of Technology.








Comments

Post a Comment

Popular posts from this blog

Information security

Image
This article is part of a series on Information security Related security categories Internet security Cyberwarfare Computer security Mobile security Network security Threats Computer crime Vulnerability Eavesdropping Malware Spyware Ransomware Trojans Viruses Worms Rootkits Bootkits Keyloggers Screen scrapers Exploits Backdoors Logic bombs Payloads Denial of service Defenses Computer access control Application security Antivirus software Secure coding Secure by default Secure by design Secure operating systems Authentication Multi-factor authentication Authorization Data-centric security Encryption Firewall Intrusion detection system Mobile secure gateway Runtime application self-protection (RASP) v t e Information security , sometimes shortened to InfoSec , is the practice of preventing unauthorized access, use, disclosure, disruption, modification, inspection, recording or destruction of information. Th
Read more

章鱼与海女图

Image
本条目 可参照英語維基百科相應條目来扩充 。 （2014/5/25） 若您熟悉来源语言和主题，请协助参考外语维基扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记 {{Translated page}} 标签。 本条目 需要擴充。 （2013年8月15日） 请協助改善这篇條目，更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。 《 章鱼与海女 》（日语： 蛸と海女 ／ たことあま   Tako to ama ）是一幅由日本畫家葛饰北斋创作的浮世绘，出自1814年（文化4年）出版的艳本《喜能会之故真通》（日语： 喜能会之故真通 ／ きのえのこまつ   Kinoe no Komatsu ）。畫中有兩隻章鱼以觸手攻擊一名採珠的海女，並進行擬似戀獸癖的交媾行為。作品尺寸为6½" × 8¾" （16.51 cm × 22.23 cm）。 [1] 在此之前的类似作品还有北尾重政的艳本《謡曲色番組》及勝川春潮的艳本《艳本千夜多女志》等，有被北斋作为参考的可能性。 《章鱼与海女图》有不同英文翻译，一般称The Dream of the Fisherman's Wife，又作Girl Diver and Octopi、Diver and Two Octopi，Richard Douglas Lane称其为 Girl Diver and Octopi [2] ，Mathi Forrer 称其为 Pearl Diver and Two Octopi [3] ，Danielle Talerico 称其为 Diver and Two Octopi 。 [4] 目录 1 作品介绍 1.1 画中对话 1.2 解释 2 评价 3 影响 3.1 模仿作品 4 另见 5 参考来源 6 外部連結 作品介绍 画中对话 原文 译文 大蛸： いつぞハいつぞハとねらいすましてゐたかいがあつて、けふといふけふ、とうとうとらまへたア。てもむつくりとしたいいぼぼだ。いもよりハなをこうぶつだ。サアサア、すつてすつてすいつくして
Read more

Farm Security Administration

Image
Farm Security Administration Farm Security Administration logo Agency overview Formed September 1, 1937  ( 1937-09-01 ) Preceding agencies Resettlement Administration Federal Emergency Relief Administration Dissolved 1946 Superseding agency Farmers Home Administration Key documents Farm Security Act Bankhead-Jones Farm Tenant Act The Farm Security Administration ( FSA ) was a New Deal agency created in 1937 to combat rural poverty during the Great Depression in the United States. It succeeded the Resettlement Administration (1935–1937). [1] The FSA stressed "rural rehabilitation" efforts to improve the lifestyle of sharecroppers, tenants, very poor landowning farmers, and a program to purchase submarginal land owned by poor farmers and resettle them in group farms on land more suitable for efficient farming. Critics, including the Farm Bureau, strongly opposed the FSA as an experiment in collectivizing agriculture—that is, in bringing
Read more