Oleg Zabluda's blog
Thursday, May 04, 2017
 
Parity, Circuits, and the Polynomial-Time Hierarchy (1981) Furst, Saxe, Sipser
Parity, Circuits, and the Polynomial-Time Hierarchy (1981) Furst, Saxe, Sipser
"""
Constant-depth circuits elegantly model programmable logic arrays (PLA's),
a type of integrated circuit used inside microprocessors to compactly represent
many functions. According to folklore, some common functions, e.g., parity,
multiplication, and transitive closure cannot be implemented with small PLA's.
The new lower bound establishes a basis for this belief by showing that any PLA
implementing, these functions must be using more than a polynomial amount of
chip area.
"""
https://wiki.epfl.ch/edicpublic/documents/Candidacy%20exam/Furst%20Saxe%20Sipser%20-%201984%20-%20Parity%20circuits%20and%20the%20polynomial-time%20hierarchy.pdf
https://wiki.epfl.ch/edicpublic/documents/Candidacy%20exam/Furst%20Saxe%20Sipser%20-%201984%20-%20Parity%20circuits%20and%20the%20polynomial-time%20hierarchy.pdf

Labels:


- posted by Oleg Zabluda @ 9:15 AM | permalink | | | technorati | bloglines | feedster

Powered by Blogger