Characterizing non-deterministic circuit size
Mauricio Karchmer, Avi Wigderson · 1993
Consider the following simple communication problem.Fix a universe U and a family Ω of subsets of U .Players I and II receive, respectively, an element a ∈ U and a subset A ∈ Ω.Their task is to find a subset B of U such that |A ∩ B| is even and a ∈ B. With every Boolean function f we associate a collection Ω f of subsets of U = f -1 (0), and prove that its (one round) communication complexity completely determines the size of the smallest nondeterministic circuit for f .We propose a linear algebraic variant to the general approximation method of Razborov, which has exponentially smaller description.We use it to derive four different combinatorial problems (like the one above) that characterize N P .These are tight, in the sense that they can be used to prove super-linear circuit size lower bounds.Combined with Razborov's method, they present a purely combinatorial framework in which to study the P vs. N P vs. co -N P question.