Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 124 / 3

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.