Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 6 2 d Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Fix an arbitrary finite and use the Banach space of bounded continuous functions with the supremum norm. Set . For in this space, the velocity integralis bounded by . If , the integrands converge pointwise and are bounded by the integrable function . The dominated convergence theorem proves continuity. Thus the rank-one gain on bounded continuous functions, , is continuous and bounded. The same theorem applied to the time integral shows that maps this space into itself, including at .
Time ordering gives the factorial bound for a Volterra iterate:Consequently the Volterra series for the linear Boltzmann equationconverges uniformly on the whole finite time slab, so its sum is continuous and bounded and satisfies the fixed point equation. Tracking the damping factors gives the sharper pointwise bound . This proves existence for every finite , without requiring or uniform continuity of . Boundedness on finite slabs does not assert a uniform bound over infinite time.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 6 2 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Separate the transported initial datum from the gain term. Defineand the Boltzmann Volterra operatorThe Duhamel principle makes the linear Boltzmann equation equivalent, whenever the integrals and solution are legitimate, toThe gain samples velocities at the backward spatial position of the outgoing velocity ; replacing that spatial shift by one depending on would give a different equation.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 6 2 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The damped free-transport evolution is . Substituting it into the Duhamel principle givesThe spatial shifts all follow the same backward characteristic curve ending at at time ; the velocity is constant.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 6 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
For a linear spatial operator, let denote the formal homogeneous evolution from time to time , satisfying and . This also allows time-dependent coefficients in the spatial operator. The Duhamel principle statesDifferentiation of the integral contributes at its upper endpoint and times the integral, while the initial value is . If is time-independent, one writes . The principle uses linearity; an arbitrary nonlinear differential operator would not justify this superposition formula. No analytic construction of or boundary conditions is required for this formal statement.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 6 1 f Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The finite- assertion needs the zero-divergence hypothesis from the preceding part, which is not repeated in this part's printed hypotheses. The norm is on , and finite conservation requires to belong to the corresponding Lp space in addition to its smoothness.
Writing for the characteristic flow map, the general solution is . A change of variables givesThus the Lp conservation for incompressible transport isWithout that condition the requested conclusion is false: the force in part (c), together with any nonzero smooth integrable initial datum given by a Gaussian function, gives . The essential supremum is still conserved by a complete invertible flow, because composition does not change the range of values.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 6 1 e Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Let along one characteristic curve. Differentiating the characteristic equation gives , , with . The Liouville formula for a fundamental matrix then gives the phase-space flow JacobianIndeed , since is independent of . Differentiation proves . If that divergence vanishes, gives and the flow preserves Lebesgue measure on phase space.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 6 1 d Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Differentiating the explicit characteristic flow map gives the block triangular Jacobian matrixIts Jacobian determinant is the product of its diagonal block determinants. Therefore
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 6 1 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
For this force, , hence and . Invert the characteristic flow map: the initial velocity for an endpoint is , and the initial position is . Constancy along each characteristic curve givesThere is no amplitude factor here: this is scalar advection, not the conservative continuity equation for a compressible density.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 6 1 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Put and . On a small closed time interval and a closed ball around the initial point, let bound and let be its spatial Lipschitz constant. The mapsends the corresponding closed ball of continuous paths into itself when the time length times is at most the ball radius. If the time length times is less than one, it is a contraction in the supremum norm. The Banach fixed-point theorem gives a local solution and uniqueness; differentiating its integral equation gives the ordinary differential equation. Overlapping local solutions agree by this uniqueness.
For continuation, the growth assumption gives, on any bounded time interval,for forward time, with the analogous reversed-time bound. The Gronwall inequality bounds the trajectory on that interval. A finite terminal time is impossible: within the resulting compact ball the field is bounded, so the path has a limit at the endpoint, and the local construction restarts there. This proves the global characteristic flow under linear growth. No differentiability of the flow with respect to its initial point is needed for this existence and uniqueness proof.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 6 1 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The characteristic equations for a transport equation on phase space areA sufficient global hypothesis is that is continuous in time, locally Lipschitz continuous in uniformly on compact time intervals, and, for every finite , satisfies for . These hypotheses give unique characteristic curves for all real times if the field is defined for all real times. It suffices for forward existence to impose them on nonnegative time. One may strengthen the spatial hypothesis to when differentiating the characteristic flow map below. Local Lipschitz continuity alone guarantees only local existence; the linear-growth bound prevents finite-time escape.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 59 4 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
A query certificate for input is a subset of coordinates such that every agreeing with on has the same value of . Define certificate complexity of a Boolean function byIf no input has output , take . Unlike a decision tree, a query certificate may be selected with full knowledge of the input.
Take a full star graph centered at , containing all incident edges and no others. For any edge not incident to , changing only its bit from zero to one destroys the common-center graph property: two spokes already force as the only possible common endpoint. Therefore every positive query certificate for this input must include every nonincident edge bit, otherwise this one-bit change would preserve its answers but change the output. There are such bits. Conversely, fixing all those bits to zero suffices for a query certificate, because all remaining edges are incident to . HenceThe upper bound for holds for any accepted graph by choosing any valid center and certifying its nonincident edges absent.
For completeness, the negative side is much smaller. Given a graph with no common center, choose a present edge , an edge not containing , and an edge not containing . These at most three present edges have empty common intersection and certify rejection. A triangle with isolated additional vertices needs all three of its present edges: with at most two queries, set every unqueried edge absent and the remaining present edges share a vertex. Thus the certificates for the common-center graph property satisfy
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 59 4 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Let be the number of independent undirected-edge bits; use unordered pairs . The paper's common-center graph property means that all present edges share a vertex. Isolated vertices are allowed, and the empty graph satisfies the property. This convention matters in the count.
The empty graph contributes to the alternating sum. The one-edge graphs contribute . A graph with at least two edges and a common center has a unique center, since two different edges have just that common endpoint. For a fixed center, its possible edge sets are subsets of the incident edges. Their contribution after removing sets of size zero and one isThese graphs are counted once for each of their unique centers. Thus the alternating count of common-center graphs isPart (a) gives , while querying all bits always suffices. ThereforeThe relevant input length is , not the number of graph vertices.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 59 4 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
A decision tree queries individual input bits, chooses subsequent queries from previous answers and labels each leaf with an output. Its decision-tree depth is the largest number of queries on any root-to-leaf path; is the least such depth over trees computing . An evasive Boolean function on bits has .
Remove repeated queries along any path, since their answers are already known. A leaf at depth fixes bits and leaves at least one bit free. The inputs reaching it form a subcube on which is constant, say . Its contribution to the alternating sum isHere is the Hamming weight. The leaf subcubes partition the input cube, so adding their contributions provesThe contrapositive is the alternating-sum criterion for decision-tree evasiveness: a nonzero alternating sum forces all bits to be necessary in the worst case.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 59 3 d Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The class NC1 consists of languages having polynomial-size, bounded-fan-in Boolean circuit families of depth . Under a uniform convention one requires the wiring to be constructible in logarithmic space; the construction below meets that requirement as well as the nonuniform one.
Write a length- binary input with most significant bit first as . Since ,Represent residues zero, one and two by two bits, respectively . Each input produces residue zero when it is zero; when it is one it produces residue one or two according to the parity of . This uses only constants and wires.
A two-residue addition modulo three is a fixed function of four Boolean variables and has a constant-size, constant-depth bounded-fan-in Boolean circuit. Define its unused encodings arbitrarily; valid inputs always produce a valid residue encoding. Use a balanced binary tree of these adders, padding with zero residues to a power of two. There are adders and layers. A final constant-size gate checks that the residue is .
This balanced finite-monoid reduction circuit is uniform: leaf signs follow index parity and internal connections follow the indices in the balanced tree, all calculable in logarithmic space. Leading zeros cause no difficulty; the empty input can be assigned the zero-integer constant convention. Consequently
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 59 3 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The AND-NOT circuit value problem belongs to P: validate the Boolean circuit and evaluate its gates in a topological ordering. Evaluation takes polynomial time even if its description is not already in a topological ordering.
For P-completeness we use logspace many-one reductions. Start from the supplied circuit value problem over the usual AND (logical conjunction), OR (logical disjunction) and NOT (negation) basis. Retain AND and NOT gates, and replace every OR gate by the De Morgan's laws gadgetThis adds only a constant number of gates per old gate, preserves its truth value for all inputs and keeps the Boolean circuit acyclic. If the format includes constant source nodes, replace them by additional input nodes assigned fixed bits zero and one; these are inputs, not disallowed gates. Larger fan-in gates can first be replaced by binary trees of their inputs.
To output the new description, keep the old gate index and a constant-size gadget position, rescan old references when necessary, and assign consistent new indices to each gadget's terminal output. These counters and references occupy bits; the input assignment is copied with any constant-source bits appended. Thus the construction is a logspace many-one reduction preserving acceptance. Since Boolean circuit Value is P-complete under such reductions,
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 59 3 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
For each fixed input length, take the complete truth table of the language. For every accepted string , form the mintermAn OR of these minterms equals the indicator function, since precisely at . This is the truth-table upper bound for circuit size.
Generate the negated input wires once and share them. With accepted strings, use at most binary AND gates and binary OR gates, besides the negations. Empty truth tables use a constant-zero Boolean circuit; length zero is handled by a constant Boolean circuit. ThusThis is an existence bound for a nonuniform circuit family, even when the language is undecidable. It supplies no algorithm for computing the truth tables of an arbitrary language.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 59 3 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
A circuit size class consists of languages whose length- indicator functions have Boolean circuits of size at most , for all sufficiently large , over a fixed finite bounded-fan-in complete basis. The notation allows a constant factor. Input-node counting conventions do not affect the polynomial and exponential bounds here.
The nonuniform class P/poly isThere is no requirement that a uniform algorithm construct the Boolean circuits. Equivalently, a polynomial-time machine can receive polynomial-length advice depending only on the input length, and the advice need not be computable.
Choose an undecidable set , for example the set in the halting problem of indices of machines that halt on empty input, and define . For each length , use a constant-zero Boolean circuit if , and an AND of all input bits if . These Boolean circuits have size and accept exactly . Thus undecidable unary languages with linear-size circuits belong to P/poly.
Every NP language is decidable by enumerating its finitely many polynomial-length certificate encodings and running the polynomial-time verifier. If were decidable, testing would decide , a contradiction. ThereforeThis separates the classes in the stated direction; it does not claim that NP is not contained in P/poly.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 59 2 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-11-05
Here a directed cycle has at least one edge. If zero-length paths were treated as cycles, an edgeless one-vertex graph would already satisfy the predicate; that convention would give the trivial nonempty-graph predicate instead of the intended directed cycle detection problem.
For NL membership, guess a starting vertex , follow a guessed directed walk for between one and edges, and accept if it returns to . Store only the start, current vertex and step counter. A graph with a nonempty closed walk contains a simple directed cycle of at most edges, including a self-loop if present. Thus the algorithm uses logarithmic space and is complete for the predicate.
For hardness, reduce the directed graph reachability problem to cycle detection. Form and add the single backward arcAll layering arcs advance exactly one layer, including the waiting arcs , so the layered graph alone is a directed acyclic graph. Any cycle in the augmented graph must contain the backward arc and therefore contains a path from to .
If is reachable from in , use a simple path of length at most and pad it with waits to exactly steps. It becomes the required layered path and closes to a cycle. Conversely, projecting such a layered path and deleting waits gives a walk from to in . This includes the case , where reachability has a zero-length witness but the augmented graph has a genuinely positive-length cycle.
There are vertices and polynomially many arcs. A transducer enumerates pairs/layers and checks old adjacency by scanning its input, using only bits. Hence this is a logspace many-one reduction, proving
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 59 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
With a read-only input tape, deterministic space complexity class consists of languages decidable by deterministic Turing machines using work-tape cells. The nondeterministic space complexity class uses Nondeterministic Turing machines, with the bound holding on every computation path and acceptance meaning that some path accepts. Input storage is not charged. We use the standard finite-state, fixed-alphabet model.
The Savitch theorem isFirst suppose a work-space budget is available. A configuration graph for computations restricted to cells has configurations encoded in bits: work contents, control state and head positions, including bits for the input head. Its size is at most for a machine-dependent constant . Add accept and exit sinks if needed; the size bound merely changes . A reachable configuration has a simple path of length smaller than the number of configurations.
For encoded configurations , define to ask whether a path of length at most exists. At , test equality or one transition. For , enumerate every candidate middle configuration and testAny path of the given length can be split into two halves of length at most ; conversely concatenation gives a path of length at most . This proves the recursion. Taking suffices. Depth is , and each recursive frame stores only its endpoints, the current middle configuration and counters in bits. The two recursive calls are made sequentially and reuse their space. The total is , even though the time can be very large.
The printed hypothesis does not say that is computable. The space-bound discovery by exit reachability removes that issue. Begin with and use the preceding recursion to test both whether an accepting state is reachable within the budget and whether a reachable state has a transition leaving the budget. Accept in the first case. If acceptance is absent and an exit is reachable, double and repeat. If neither is reachable, reject: all computations remain within this finite configuration graph, and none accepts.
Every path of the original machine uses at most cells. Once reaches that bound there can be no reachable exit, so this procedure terminates. The final budget is by doubling, and all stages reuse the same storage. Hence its deterministic space is without requiring a machine that first computes . This proves the stated general form.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 59 1 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
A proposed assignment for 2UN-SAT can be checked in polynomial time, including checking the syntactic restriction, so the language belongs to NP.
For an explicit reduction, parse any Boolean formula into a Boolean circuit over binary AND (logical conjunction), binary OR (logical disjunction) and unary NOT (negation), and apply the gate equivalences in part (a), asserting its output. Every gate clause has at most two positive literals: the AND clauses have respectively one, one and one; the OR clauses have one, one and two; and the NOT clauses have two and zero. The unit output/constant clauses also obey the restriction. Hence the resulting formula is an instance of 2UN-SAT.
The Tseitin transformation is linear in the gate description, and its auxiliary variables enforce the gate values rather than relaxing their relation to the inputs. Therefore the original formula is satisfiable if and only if the transformed restricted formula is satisfiable. This is a polynomial-time many-one reduction from SAT, whose hardness follows from the Cook-Levin theorem. ConsequentlyThe condition limits positive literals, without limiting total clause length.
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact





