Lupanov representation

Lupanov's (k, s)-representation, named after Oleg Lupanov, is a way of representing Boolean circuits so as to show that the reciprocal of the Shannon effect. Shannon had showed that almost all Boolean functions of n variables need a circuit of size at least 2nn−1. The reciprocal is that:

All Boolean functions of n variables can be computed with a circuit of at most 2nn−1 + o(2nn−1) gates.

Definition

The idea is to represent the values of a boolean function ƒ in a table of 2k rows, representing the possible values of the k first variables x1, ..., ,xk, and 2n−k columns representing the values of the other variables.

Let A1, ..., Ap be a partition of the rows of this table such that for i < p, |Ai| = s and . Let ƒi(x) = ƒ(x) iff x ∈ Ai.

Moreover, let be the set of the columns whose intersection with is .

gollark: And if your bot supported IRCv3 and my server also did, it could get history replay!
gollark: It will be.
gollark: kitwho buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack buffer overflow attack
gollark: kitwho CTCP BEE_DEPLOYMENT_INITIALIZED
gollark: kitwho version implode

See also
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.