Constant Depth Circuits and the Lutz Hypothesis

Resource-bounded measure theory is a study of complexity classes via an adaptation of the probabilistic method. The central hypothesis in this theory is the assertion that NP does not have measure zero in Exponential Time. This is a quantitative strengthening of NP/spl ne/P. We show that the analog in P of this hypothesis fails dramatically. In fact, we show that NTIME[n/sup 1/11/] has measure zero in P. These follow as consequences of our main theorem that the collection of languages accepted by constant-depth nearly exponential-size circuits has measure zero at polynomial time. In contrast, we show that the class AC/sup 0//sub 4/[/spl oplus/] of languages accepted by depth-4 polynomial-size circuits with AND, OR, NOT, and PARITY gates does not have measure zero at polynomial time. Our proof is based on techniques from circuit complexity theory and pseudorandom generators.

Authors

• Jin-Yi Cai
• D. Sivakumar
• Martin J. Strauss

Keywords

• Circuits
• Time measurement
• Polynomials
• Size measurement
• Complexity theory
• Computer science
• Natural languages
• Boolean functions
• Particle measurements
• Constant Depth
• Circuit Depth
• Constant-depth Circuits
• Pseudo-random
• Measure Zero
• Gambling
• Language Teaching
• Complex Class
• Sample Space
• Submatrix
• Probabilistic Method
• Word Length
• Intuitive Understanding
• Forward Error Correction
• Lebesgue Measure
• String Length
• Exponential Time
• Probabilistic Process
• Boolean Function
• Total Capital
• OR Gate
• NOT Gate
• Circuit Size
• Output Bits
• Gaussian Elimination
• Measurement Theory
• Proof Of The Existence