Editing Linear separability (section)

== Linear separability of Boolean functions in ''n'' variables ==

A [[Boolean function]] in ''n'' variables can be thought of as an assignment of ''0'' or ''1'' to each vertex of a Boolean [[hypercube]] in ''n'' dimensions. This gives a natural division of the vertices into two sets. The Boolean function is said to be ''linearly separable'' provided these two sets of points are linearly separable. The number of distinct Boolean functions is <math>2^{2^{n}}</math>where ''n'' is the number of variables passed into the function.<ref>{{Cite book|title=Artificial intelligence a modern approach|author=Russell, Stuart J.|others=Norvig, Peter 1956-|year=2016|isbn=978-1292153964|edition= Third|location=Boston|pages=766|oclc=945899984}}</ref>

Such functions are also called linear threshold logic, or [[Perceptron|perceptrons]]. The classical theory is summarized in,<ref>{{Cite book |last=Muroga |first=Saburo |title=Threshold logic and its applications |date=1971 |publisher=Wiley-Interscience |isbn=978-0-471-62530-8 |location=New York}}</ref> as Knuth claims.<ref>{{Cite book |last=Knuth |first=Donald Ervin |title=The art of computer programming |date=2011 |publisher=Addison-Wesley |isbn=978-0-201-03804-0 |location=Upper Saddle River |pages=75–79}}</ref>

The value is only known exactly up to <math>n=9</math> case, but the order of magnitude is known quite exactly: it has upper bound <math>2^{n^2 - n \log_2 n + O(n)}</math> and lower bound <math>2^{n^2 - n \log_2 n - O(n)}</math>.<ref name=":0">{{Cite journal |last1=Šíma |first1=Jiří |last2=Orponen |first2=Pekka |date=2003-12-01 |title=General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results |url=https://direct.mit.edu/neco/article/15/12/2727-2778/6791 |journal=Neural Computation |language=en |volume=15 |issue=12 |pages=2727–2778 |doi=10.1162/089976603322518731 |pmid=14629867 |s2cid=264603251 |issn=0899-7667}}</ref> 

It is [[co-NP-complete]] to decide whether a Boolean function given in [[Disjunctive normal form|disjunctive]] or [[conjunctive normal form]] is linearly separable.<ref name=":0" />

{| class="wikitable"
|+<small>Number of linearly separable Boolean functions in each dimension</small><ref>
{{cite document
| last=Gruzling
| first=Nicolle
| title=Linear separability of the vertices of an n-dimensional hypercube. M.Sc Thesis
| publisher= University of Northern British Columbia
| year=2006
}}</ref> {{OEIS|id=A000609}}
!Number of variables
!Boolean functions
!Linearly separable Boolean functions
|-
|  2 
|16|| 14
|-
|  3 
|256|| 104
|-
|  4 
|65536|| 1882
|-
|  5 
|4294967296|| 94572
|-
|  6 
|18446744073709552000|| 15028134
|-
|  7 
|3.402823669 ×10^38
| 8378070864
|-
|  8 
|1.157920892 ×10^77|| 17561539552946
|-
|  9 
|1.340780792 ×10^154|| 144130531453121108
|}