Exploring Circuit Size Bounds in Complexity Theory
The article delves into Shannon's Theorem in Complexity Theory, discussing the upper bounds of circuit sizes for Boolean functions of n variables. It explores the 1-1 correspondence with 0-1 strings of length 2n and how Boolean functions can be expressed as CNF or DNF formulas. The computation of the AND of n variables and negated variables by circuits is examined, shedding light on the overall complexity in circuit size constraints.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CMSC 281Complexity Theory Shannon s Theorem
Circuit Size Bounds How big can circuit size be?
Circuit Size Bounds How big can circuit size be? (S(n) size of optimal circuit family) Boolean functions of n Boolean variables are in 1-1 correspondence with 0-1 strings of length 2n
Circuit Size Bounds How big can circuit size be? (S(n) size of optimal circuit family) Boolean functions of n Boolean variables are in 1-1 correspondence with 0-1 strings of length 2n (the i-th bit of the string is the value of the function on bin(i), the bit pattern of length n that is the binary representation of the number i)
Circuit Size Bounds How big can circuit size be? (S(n) size of optimal circuit family) Boolean functions of n Boolean variables are in 1-1 correspondence with 0-1 strings of length 2n (the i-th bit of the string is the value of the function on bin(i), the bit pattern of length n that is the binary representation of the number i) So there are 2 to the power 2n Boolean functions of n variables.
Circuit Size Bounds Upper Bounds We saw that every Boolean function can be expressed as a CNF (or DNF) formula. The AND of n variables and negated variables can be computed by a circuit of size O(n)
Circuit Size Bounds Upper Bounds We saw that every Boolean function can be expressed as a CNF (or DNF) formula. The AND of n variables and negated variables can be computed by a circuit of size O(n) There are at most 2nsuch terms. (actually, only 2n-1)
Circuit Size Bounds Upper Bounds We saw that every Boolean function can be expressed as a CNF (or DNF) formula. The AND of n variables and negated variables can be computed by a circuit of size O(n) There are at most 2nsuch terms. (actually, only 2n-1) OR-ing them together takes O(2n) more gates.
Circuit Size Bounds Upper Bounds We saw that every Boolean function can be expressed as a CNF (or DNF) formula. The AND of n variables and negated variables can be computed by a circuit of size O(n) There are at most 2nsuch terms. (actually, only 2n-1) OR-ing them together takes O(2n) more gates. O(n 2n) gates altogether.
Circuit Size Bounds Upper Bounds We saw that every Boolean function can be expressed as a CNF (or DNF) formula. The AND of n variables and negated variables can be computed by a circuit of size O(n) There are at most 2nsuch terms. (actually, only 2n-1) OR-ing them together takes O(2n) more gates. O(n 2n) gates altogether. Can do better (Lupanov) --- O(2n/ n) gates (tricky)
Circuit Size Lower Bounds Shannons Theorem Shannon s Theorem (1949) There is a Boolean function that requires a circuit of size (2n/ n).
Circuit Size Lower Bounds Shannons Theorem Shannon s Theorem (1949) There is a Boolean function that requires a circuit of size (2n/ n). (he was more precise, and proved it for almost all )
Circuit Size Lower Bounds Shannons Theorem Shannon s Theorem (1949) There is a Boolean function that requires a circuit of size (2n/ n). Proof sketch: we can represent a Boolean circuit as a collection of gates using adjacency lists
Circuit Size Lower Bounds Shannons Theorem Shannon s Theorem (1949) There is a Boolean function that requires a circuit of size (2n/ n). Proof sketch: we can represent a Boolean circuit as a collection of gates using adjacency lists If the size of the circuit is S, this requires < 9S logS bits. So the number of these circuits is < 2 9S logS
Circuit Size Lower Bounds Shannons Theorem Shannon s Theorem (1949) There is a Boolean function that requires a circuit of size (2n/ n). Proof sketch: we can represent a Boolean circuit as a collection of gates using adjacency lists If the size of the circuit is S, this requires < 9S logS bits. So the number of these circuits is < 2 9S logS Assume S=2n/10n.
Circuit Size Lower Bounds Shannons Theorem Shannon s Theorem (1949) There is a Boolean function that requires a circuit of size (2n/ n). Proof sketch: we can represent a Boolean circuit as a collection of gates using adjacency lists If the size of the circuit is S, this requires < 9S logS bits. So the number of these circuits is < 2 9S logS Assume S=2n/10n. Substituting, we get fewer than 2 to the power 2n, the number of Boolean functions
Circuit Size Lower Bounds Shannons Theorem Shannon s Theorem (1949) There is a Boolean function that requires a circuit of size (2n/ n). Proof sketch: we can represent a Boolean circuit as a collection of gates using adjacency lists If the size of the circuit is S, this requires < 9S logS bits. So the number of these circuits is < 2 9S logS Assume S=2n/10n. Substituting, we get fewer than 2 to the power 2n, the number of Boolean functions Actually, almost all Boolean functions require this many gates!
Circuit Size Lower Bounds Shannons Theorem Shannon s Theorem (1949) There is a Boolean function that requires a circuit of size (2n/ n). Actually, almost all Boolean functions require this many gates! So why can t we find one?
Circuit Size Lower Bounds Shannons Theorem Shannon s Theorem (1949) There is a Boolean function that requires a circuit of size (2n/ n). Actually, almost all Boolean functions require this many gates! So why can t we find one? Looking for hay in a haystack .
