Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 124 (Introduction to Computational Complexity)

Use the following decision-tree adversary for a threshold function. Regardless of which variables the tree queries, answer $0$ on the first $n-r$ queries and $1$ on the next $r-1$ queries. After any proper prefix of this answer sequence, the unqueried variables can be completed both to an input of weight below $r$ and to one of weight at least $r$. Immediately before the last query the answers contain exactly $n-r$ zeros and $r-1$ ones, so the final bit alone determines the value of the threshold Boolean function $f_{n,r}$. Thus every decision tree has a root-to-leaf path of length $n$, while querying all variables gives depth $n$. Hence

In one standard form, the Håstad switching lemma says that if $F$ is a $k$-DNF and $\rho$ is a random restriction that independently leaves each variable unset with probability $p$ and otherwise assigns it a uniform Boolean value, thenThe dual statement exchanges DNF and CNF. Thus a small-width DNF becomes, with high probability, a shallow decision tree and hence a small-width CNF after a sufficiently sparse random restriction.

We use the following consequence of the Håstad switching lemma. If an unbounded-fan-in layered AND/OR circuit has depth $d$ and size $S$, then after $d-1$ successive independent random restrictions, each retaining a suitably small proportion $p=\Theta (1/\log S)$ of the currently live variables, the restricted circuit is constant on the leaves of a decision tree of bounded depth with probability at least $3/4$. To prove this switching-lemma depth reduction, first express the bottom layer as DNFs or CNFs, truncate any term wider than $O(\log S)$ because a random assignment satisfies or kills it except with probability $S^{-O(1)}$, and then apply the switching lemma with a union bound over at most $S$ gates. Replace each surviving bottom gate by its decision tree, switch DNF to CNF or conversely, and repeat. Choosing the constants so each round fails with probability at most $1/(4d)$ proves the claim by a union bound.

Suppose now that $S=\exp (o(n^{1/(d-1)}))$. After the $d-1$ rounds, the expected number of live variables isA Chernoff bound shows that at least $N/2$ variables remain live with probability tending to one. Conditional on the set of live variables, the assigned variables contain, with probability bounded away from zero, sufficiently close to half zeros and half ones that the restricted majority function remains a nonconstant threshold function on $\Omega (N)$ live variables. By part (i), its decision-tree depth is then $\Omega (N)$.

With positive probability both conclusions hold: the restricted circuit has bounded decision-tree depth, but the function it computes has depth tending to infinity. This contradiction provesFor each fixed depth, the constants in the reduction may be chosen uniformly to give an absolute positive constant after the usual depth convention is fixed.

For a family $A\subseteq [n{]}^{(\le l)}$, let $⟨A⟩$ be the set of graphs on $[n]$ containing the clique on some $W\in A$. Write $A^{\ast }$ for its Razborov closure: whenever $W_1,\dots ,W_r\in A$ andwith all sets of size at most $l$, closure adjoins $W$. A family is $r$-closed when $A=A^{\ast }$.

For closed $A,B$, define the lattice operationsThe corresponding error sets are

The Razborov gate-by-gate approximation lemma says that if a monotone circuit of size at most $M$ computes a graph family $S$, and $\tilde{S}$ is obtained by evaluating the same circuit with $\square ,\bigsqcup$, then there are at most $M$ pairs of intermediate lattice elements such thatThis follows by induction through the circuit: an AND gate can introduce only a ${\delta }_{\cap }$ error, and an OR gate only a ${\delta }_{\cup }$ error.

We first need the minimal-member bound for a Razborov-closed family: an $r$-closed family has at most $(r-1{)}^k$ inclusion-minimal members of size $k$. Indeed, its minimal members of size at most $k$ cannot contain $r$ sets whose pairwise intersections lie inside a proper subset of another minimal member, since closure would then contain that proper subset. The resulting set-system bound is proved by induction on $r$: fix one member $D$, partition the remaining members according to their intersections $C\subseteq D$, delete $C$, and apply the $(r-1,k-|C|)$ bound in each class. Summing over $C$ gives

If $⟨A⟩$ is not the set of all graphs, no inclusion-minimal member of $A$ has size zero or one. Every $m$-clique in $⟨A⟩$ contains a minimal $W\in A$, so the number of such cliques is at mostDividing by $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ and usingthe assumed $2(r-1)m\le n$ gives a proportion at mostThus either $⟨A⟩$ is universal or it contains at most half of all $m$-cliques.

Let an $m$-clique on vertex set $Z$ belong toThen $Z$ contains minimal members $X\in A$ and $Y\in B$, but contains no member of $A\cap B$. If $|X\cup Y|\le l$, upward closure of both closed families would put $X\cup Y$ in $A\cap B$, a contradiction. Hence $|X\cup Y|>l$, so either $|X|>l/2$ or $|Y|>l/2$.

Using the minimal-member bound from part (ii), the number of possible $Z$ is at mostAfter division by $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ and use of $2(r-1)m\le n$, this is at most

Put $C=A\cup B$. ThenGenerate a uniformly random complete $(m-1)$-partite graph by independently assigning one of $m-1$ colours to each vertex and joining vertices of different colours. Such a graph contains the clique on $W$ exactly when the colouring is injective on $W$.

Construct $C^{\ast }$ by adjoining one forced set at a time. There are at most $n^l$ possible sets of size at most $l$. If $W$ is newly forced by $W_1,\dots ,W_r$, then, conditional on $W$ being rainbow, the events that each $W_i$ is not rainbow depend on disjoint petals $W_i\setminus W$. Since $l^2\le m$, each has conditional probability at most $1/2$. Their simultaneous probability is therefore at most $2^{-r}$. A union bound over the at most $n^l$ closure steps givesThis is exactly the claimed proportion of complete $(m-1)$-partite graphs.

Let a monotone circuit of size $M$ compute the $m$-clique function, and let $\tilde{S}=⟨A⟩$ be its lattice approximation from part (i). If $\tilde{S}$ is not universal, part (ii) says that it misses at least half of all positive $m$-cliques. The approximation lemma and part (iii) then implyIf $\tilde{S}$ is universal, every complete $(m-1)$-partite graph is a negative input that must be covered by a union-error set. Part (iv) givesThereforeChoosewith constants satisfying the two hypotheses and $r>2l{\log }_{2}n$. Both lower bounds are thenSince the graph has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ input variables, this is exponential in a positive power of the number of inputs, up to a logarithmic factor.

As Boolean functions on edge indicators,Thus $g_m$ is the dual Boolean function of the clique function. Given a monotone circuit for $g_m$, swap every AND gate with an OR gate and swap the constants zero and one. De Morgan's laws show that the resulting circuit has the same size and computes ${\mathrm{CLIQUE}}_{n,m}$. The lower bound from part (v), with the same choice of $m$, therefore applies to $g_m$.

Take the three rank-one quadratic formsThe first two already give $ac$ and $bd$, whileHence all three required polynomials lie in their linear span.

Split two $2^{k+1}$-digit numbers into high and low halves:where $B$ is the base raised to $2^k$. Their product isThe Karatsuba multiplication identitycomputes the three required half-size products $ab$, $cd$, and $(a+c)(b+d)$, soSince $f(0)=1$, induction gives $f(k)\le 3^k$. For $n=2^k$,Padding an arbitrary input length to the next power of two changes only the constant, yielding $O(n^{\alpha })$ digit multiplications with $\alpha =\log 3/\log 2$.

Write each Horn clause as an implicationwhen it has one positive literal $y$, or as a forbidden conjunctionwhen it has none. Start with every variable false. Repeatedly, whenever all antecedents of an implication are true, set its conclusion true. If a forbidden conjunction ever has all antecedents true, report unsatisfiable; otherwise stop when no change is possible and return the resulting assignment.

Each step changes a previously false variable to true, so at most the number of variables steps occur; scanning all clauses after each step is polynomial time. For correctness, every satisfying assignment must set every variable derived by this Horn-SAT forward-chaining algorithm to true, by induction over the derivation. Therefore, if the algorithm violates a negative clause, every assignment violates it. If no violation occurs, all implications and all negative clauses are satisfied by the final assignment. This proves polynomial-time decidability.

Interpret the permanent of a matrix as the total weight of the cycle covers of its weighted directed graph. Valiant's reduction builds a graph from three constant-size components.

Wire one variable port to every literal occurrence and one clause port to each literal. The balanced-occurrence hypothesis lets the true and false tracks of each variable be paired without extra weighting. A routine gadget case analysis shows that cycle covers surviving cancellation correspond to satisfying assignments, each with the same fixed multiplicity and sign. A small normalization gadget removes that fixed factor, or it can be tracked explicitly. The construction has constant size per variable, clause, and occurrence, so it is a polynomial-time counting reduction from Balanced number 3-SAT to the permanent of a $\{-1,0,1\}$ matrix.

View $M$ as a directed graph with nonnegative integer edge weights. For an edge of weightbuild a binary path-counting gadget with one entrance and one exit and exactly $w$ entrance-to-exit routes. Starting with one route, a constant-size diamond doubles the number of routes; processing the bits from most significant to least significant repeatedly doubles and, when $b_j=1$, adds one bypass route. The gadget has $O(n)$ vertices and only zero-one edges.

Add forced internal edges and self-loops so that a cycle cover not using the simulated edge extends uniquely across the gadget, whereas a cycle cover using it has exactly one extension for each entrance-to-exit route. Replacing every weighted edge therefore multiplies each original cycle cover by precisely the product of its selected edge weights. Summing over covers givesThere are $n^2$ entries and each gadget has $O(n)$ size, so $N$ is constructed in polynomial time.

A property $\mathcal{P}=({\mathcal{P}}_n)$ of $n$-variable Boolean functions is:

A property satisfying all three conditions is a natural proof. The Razborov–Rudich natural-proofs barrier states that if exponentially secure pseudorandom function families exist in $\mathrm{P}/\mathrm{poly}$, then no property that is constructive and large is useful against polynomial-size circuits.

Suppose such a property $\mathcal{P}$ existed. Given oracle access to an unknown $n$-variable function, query its full truth table and run the constructive membership test. This takes $2^{O(n)}$ time. For a truly random function, largeness makes the test accept with probability at least $2^{-O(n)}$. Repetition amplifies this to a constant acceptance probability within $2^{O(n)}$ time.

For a function drawn from the assumed pseudorandom family, each keyed function has polynomial-size circuits, so usefulness makes the test reject for the relevant lengths. The amplified membership test therefore distinguishes the pseudorandom family from a truly random function with constant advantage in exponential time, contradicting exponential pseudorandomness. Hence the three conditions cannot coexist.

Proceed by structural induction on a Boolean formula $F$. A leaf computes $x_i$ or $\neg x_i$, so its measure is $1$, equal to its leaf count. If the root is an AND gate with subformulae computing $g,h$, thenby property 2; the induction hypothesis bounds this by the sum of the two subformula sizes, which is the size of $F$. Property 3 gives the identical argument for an OR gate. Consequently every formula computing $f$ has size at least $\mu (f)$, so $\mu (f)$ is a formula-size lower bound.