Resumen de alto nivel del método de aproximaciones de Razborov

Respuestas:

6

Sea f una función booleana en n bits. Sea Z = f - 1 ( 0 ) 2 n . Sea C un circuito en n bits y de tamaño m y puertas g 1 , ... , g m . g i también denota la función en n bits calculada por subcircuito con g i como la última puerta. Las primeras n puertas son para la entrada x 1 , ... , x nfnZ=f1(0)2nCmg1,,gmginginx1,,xn . El objetivo es mostrar que C de tamaño mCm cannot compute ff. Consider all computations of CC on inputs from ZZ. A computation assigns values to outputs of gates. Let BB be the Boolean algebra of P(Z)P(Z).

The idea is to consider for any function gg on nn-bits how well it approximates ff on ZZ. Let ||g||={wZg(w)0}||g||={wZg(w)0}.

For an ultrafilter FBFB we can define a new computation by ultraproduct from it: c(gi)=0c(gi)=0 iff ||gi||F||gi||F. Because an ultrafilter is essentially a set of consistent computations for 0 values the resulting cc is a valid computation. It would follow that f(c1,,cn)=0f(c1,,cn)=0. We created a new computation from existing ones. Since all ultrafilters on finite sets are principal c1,,cnZc1,,cnZ. This works for any circuit, we have not exploited the fact that the circuit is of size mm.

The next idea is now to exploit the finiteness of the circuit to construct a new input that is outside ZZ and f(w)0f(w)0 but the circuit does not notice because of its limited size and therefore still outputs 0. So it does not compute ff.

We need to relax the definition of ultrafilter so that we can get an input outside ZZ. In place of ultrafilters we use upward-closed subsets of BB (aFaF and abab implies bFbF) that preserve meets(a,bFa,bF implies abFabF).

Let WF={w2nwi=0||¬xi||F,wi0||xi||F}WF={w2nwi=0||¬xi||F,wi0||xi||F}. WFWF is the set of inputs consistent with FF. If FF is prime (abFabF implies aFaF or bFbF) and nonfull (FF) then for each ii, FF contains either ||xi||||xi|| or ||¬xi||||¬xi|| and WFWF contains only a single input.

We are going to relax preservation of meets. In place of all meets in the Boolean algebra we will preserve a small number of them. Let |f||f| be the smallest number kk of meets M=(a1b1,,akbk)M=(a1b1,,akbk) such that for all upward-closed, nonfull, MM-preserving FF, WFZWFZ.

Let mm be the circuit complexity of ff. Razborov proved that 12|f|mO(|f|3+n3)12|f|mO(|f|3+n3).

Note that this inequality holds for all functions. To prove a circuit size lower bound mm show that for all mm-meets MM, there is a FF that satisfies the conditions but its WFWF is not contained in ZZ. Moreover any strong circuit lower bound can be proven by this method because of the second inequality.

The actual part of a circuit lower bound proof is to show that for given mm, for any mm-meets there is such an FF. In the case of monotone circuits the condition about WFWF simplifies to wi0||xi||Fwi0||xi||F so coming up with FF is easier.

Alexander Razborov, On the Method of Approximation, 1989. pdf

Mauricio Karchmer, On Proving Lower Bounds for Circuit Size, 1995.

Tim Gowers, Razborov's method of approximation, 2009. pdf

Bob
fuente
3
What is |f||f|? Is it kk?
Emil Jeřábek
0

Disclaimer: This is only a high-level overview intended to give some intuition to the methods used in Blum's recent paper.

I will attempt to use notation that is closer to what is used in the aforementioned paper.

Let ff be a Boolean function on nn variables x1,,xnx1,,xn. Suppose we want to prove that any Boolean network computing ff has large size.

Given some Boolean network ββ computing ff at its output node, consider the following process.

  1. Order the gates in ββ according to some topological order g1,g2,,gmg1,g2,,gm where the last node is the output node.
  2. For each time step t=1,,mt=1,,m we will approximate the function computed at gate gtgt by a “simple” function fgtfgt. This approximation may change the functions computed at nodes downstream of gtgt (in particular, the function at the output node gmgm may have changed).

At the end of this process, we will have approximated the function computed at gmgm by a simple function fgmfgm.

Next construct a group of test inputs T{0,1}nT{0,1}n.

Suppose we can prove the following statements:

  • The approximation of each individual node is good (i.e., at most ee-many mistakes are introduced on inputs from TT at each approximation step).
  • No simple function approximates ff well (i.e., for any simple function fgmfgm, we have fgmffgmf on more than a dd-fraction of TT).

Then by simply counting the number of errors we get that ββ must have at least d|T|ed|T|e-many gates.

If this approximation scheme can be shown to work for any network ββ computing the function ff, then we arrive at a lower bound for the circuit complexity of ff.

alw
fuente
I don't think this answers the question, the question doesn't ask anything about that draft.
Kaveh
@Kaveh that is fair. I may have incorrectly assumed, due to the timing of the question, that it was asking about this technique in relation to the paper.
alw