Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem
share
Detecting patterns in strings and images is a fundamental and well studied problem. We study the circuit complexity of the string matching problem under two popular choices of gates: De Morgan and threshold gates. For strings of length n and patterns of length n ≪ k ≤ n -o(n), we prove super polynomial lower bounds for De Morgan circuits of depth 2, and nearly linear lower bounds for depth 2 threshold circuits. For unbounded depth and k ≥ 2, we prove a linear lower bound for (unbounded fan-in) De Morgan circuits. For certain values of k, we prove a Ω(√(n)/ n) lower bound for general (no depth restriction) threshold circuits. Our proof for threshold circuits builds on a curious connection between detecting patterns and evaluating Boolean functions when the truth table of the function is given explicitly. Finally, we provide upper bounds on the size of circuits that solve the string matching problem.
READ FULL TEXT