Why Problems Are Hard

The Fibred Order of Difficulty

Difficulty is not stored inside a problem like mass inside an object. The same state can be recoverable through one sensor and invisible through another. The same target can be reachable with one actuator and impossible with another. The same calculation can fit one memory model and exceed another.

This does not make difficulty subjective. A locked door does not open under a better description, and a false conjecture does not become true for a weak prover. Difficulty is relational because a complete claim names a task and a way of encountering it. It is real because the success or failure of that relation is constrained by the world.

Representation lives in feedback

An operative representation is whatever carries selected consequences of past interaction into the next estimate or action. It may be a posterior distribution, an observer state, a compressed transcript, or marks on paper. Its value is not its size. It is whether it preserves distinctions needed by the task. For deterministic reports, post-processing can merge indistinguishability classes but cannot split them. A finer report therefore weakly enlarges the actions that remain acceptable across every compatible state, and a quotient can make that inclusion strict.

Fix a source law for the unknown and an admitted policy whose random seed is independent of it. A representation causally built from its initial state, the full adaptive transcript, and that seed cannot contain more information about the unknown than those inputs. Processing can organize, compress, or discard evidence. It cannot invent evidence. If target accuracy requires more task-relevant information than the initial state contains, a round lower bound also needs a conditional information cap at every round. For a claim about an entire policy class, that cap must hold uniformly over every admitted policy and history.

The scalar Gaussian case makes this concrete. Repeated independent measurements add precision. Greater measurement noise means more observations are required to reach the same posterior variance. This is exact for a fixed scalar state. A dynamic Kalman filter is less simple: convergence also depends on the dynamics, process noise, observation map, and observability conditions. For continuous-time nonlinear dynamics, there is no universal Kalman observability matrix. The Hermann-Krener construction spans differentials of outputs and their iterated Lie derivatives along every admitted system vector field. Full rank is sufficient for local weak observability. With constant deficient rank and a smooth involutive annihilator, Frobenius yields local hidden leaves; a nullspace at one singular point does not. If same-input, same-output trajectories converge to each other, their hidden ambiguity is detectable. A fixed nonzero tube is practical detectability; a disturbance-gain tube that vanishes with the disturbance is a robust variant, not exact asymptotic detectability under nonzero disturbance.

Exact reconstruction is often unnecessary. If every state left indistinguishable by the admitted experiments shares one acceptable action, the agent can act robustly without knowing which state is actual. Information is task-relevant only when it changes the attainable decision.

Robustness has a margin

Nominal convergence says what an observer does inside its design model. Robustness asks what remains true when the plant, sensor, disturbance, or fault differs from that model. No robustness claim is complete until it declares the environment and model uncertainty class, its norm, and its bounds.

Suppose a one-step error inequality holds uniformly over that class, with an effective contraction factor formed from a nominal factor plus a mismatch allowance. The allowance consumes contraction margin. When the factor is below one, bounded additive disturbance gives an upper certificate: a transient plus a tube whose radius is the disturbance bound divided by the remaining margin. The tube is not an accuracy floor, nor proof that another observer cannot do better. More mismatch weakens this certificate.

If the effective factor crosses one, the contraction proof is gone. That does not prove the observer actually diverges. It means this certificate has reached its boundary. A claimed maximum degree of divergence is meaningful only inside a declared mismatch set and norm.

Fault accommodation, detection, and isolation are different. Accommodation keeps error or safety inside a bound. Detection separates faulty residuals from healthy uncertainty. Isolation separates one fault from other faults. With healthy residual radius rho, fault norm above twice rho is a sufficient deterministic detection margin at the smallest threshold certified from that radius bound alone. Candidate residual balls of radius rho are disjoint when their centers are separated by more than twice rho. These are sufficient norm bounds, not probability guarantees. A fault can be accommodated without being detected, or detected without being isolated.

High observer gain exposes the tradeoff. It can speed nominal convergence while amplifying measurement noise, making the certified robust tube larger. Fast and accurate are not the same point on the performance frontier.

Knowing does not make a path

Reachability is generated by actions. A complete map can reveal that a target is reachable and can reduce search, but it does not add a missing transformation. If a derived action only abbreviates paths already available from every state, it can shorten programs without enlarging the reachable set.

A reachable target can still require a dip in an objective. Barrier depth measures the shallowest worst dip among admissible paths. It is a bottleneck statistic, not a general cost. It does not count steps, measure energy, give search time, or determine stochastic escape probability.

Search, traversal, and possibility are therefore distinct. A path may exist but be unknown. It may be known but forbidden. It may have zero barrier and enormous length. Treating all three questions as landscape hardness hides the relevant boundary.

Behavior comes before its presentation

A differential equation, automaton, state-space model, or input/output split presents a system. In behavioral form, the system is a declared time domain, signal space, and set of admitted trajectories. Different internal models can present the same boundary behavior without being equally useful or equally faithful to the plant.

Interconnection retains trajectories compatible across shared signals, while hiding projects internal signals away. Hiding before composition can admit visible trajectories backed by incompatible hidden witnesses. If local trajectories restrict and compatible pieces have a unique admissible glue, they support a sheaf semantics on the chosen time structure. A topos can organize the resulting logic, but it does not provide the safety proof.

Safety means every admitted closed-loop trajectory remains in the safe set. For deterministic discrete dynamics this is equivalent, on the behavior generated from the safe set, to one-step forward invariance. Empty behavior is vacuously safe, so a useful controller certificate also needs nonblocking or viability.

An abstraction is usually many-to-one. Forward simulation gives valid abstract images of concrete paths. Executing an abstract plan additionally requires every abstract step to lift from the concrete state actually reached, and abstract success to reflect concrete success. Costs, pathwise safety, and barriers need their own witnesses. A new sensor, actuator, predicate, or oracle is an extension, not a relabeling.

Difficulty has a fibred order

Asymptotic complexity claims require a family of inputs, an encoding and size measure, a machine and access model, a success criterion, and a resource measure. They concern growth across the family. An exact cost, barrier, or resource-loss pair for one instance is an instance-level fact, not by itself an asymptotic theorem. A large candidate set alone is not a lower bound. One-pass input, rereadable input, and external memory define different problems.

For a fixed model, call a resource-loss pair attainable when some program stays within that resource budget and loss bound. Order pairs componentwise, with smaller resources and smaller loss better. The region is upward closed. Its nondominated attainable points, when they exist, form its attained Pareto front. Limiting boundary values may live only in the closure and never be attained. More time may buy accuracy. More memory may replace recomputation. Information limits or unreachable goals can send some required budgets to infinity.

Fix a comparison context: common task, instance and environment quantifiers, uncertainty class, admitted programs, interfaces, and resource-loss coordinates. Its ambient fibre is the powerset of its performance space, ordered by inclusion. Each encounter maps to one attainable region in that fibre. One encounter is at least as hard as another when its region is contained in the other's. This is a preorder on encounters. After equal regions are identified, the quotient is order-isomorphic only to the image of the attainable-region map, not generally to the whole ambient fibre.

The order need not be total. If neither region includes the other, the encounters are incomparable. Crossing frontiers make this visible: one may be better at coarse accuracy and worse near exactness. A scalar ranking requires an extra rule for trading resources against loss.

For a performance-point map from one context to another, preimage is monotone, contravariant, and lawful for identities and composition. It reflects inclusion when the point map is surjective, and even without more it permits a heterogeneous comparison of given encounters. But the preimage of a realized region need not be realized, so reindexing the realized difficulty classes needs closure under preimage; a compatible transport of encounters is one sufficient witness, not the only one. The direct image of a many-to-one abstraction is a separate covariant operation and may fail to reflect order. There is no topology or manifold here, and no global ranking where no performance translation has been declared. The rest is constructed rather than disclaimed: the contexts and their maps assemble into a total category, the chosen reindexing maps are exactly its canonical cartesian lifts, and each context's order sits inside it as the standard fibre. All of that is machine checked.

Finite-state lower bounds illustrate the need for exact interfaces. A machine that must retain one of many distinguishable possibilities needs at least that many states. A machine with two to the power s states has s bits of capacity, not two to the power s bits. Assuming base at least two and positive input length, the book's positional multiplication bound is really a delayed-copy bound obtained by fixing one operand to one, not a theorem that multiplication is generally hard.

Preprocessing moves work rather than erasing it. An index, proof library, or abstraction hierarchy can be costly to build and cheap to query. A fair comparison states who receives it, whether its construction is charged, and across how many instances it is reused.

One shape behind three boundaries

Three boundaries share one algebraic shape, and it is checked. What actions can reach, what an observation cannot tell apart, and what remains of behavior after hiding a signal are all closures: closing twice is the same as closing once. That is why adding an already reachable move adds nothing and why a statistic computed from an existing report distinguishes nothing new. The shape has proved limits too. Hiding does not commute with joining components, and a closure in one context need not agree with reindexing into another; both failures come with small finite counterexamples.

There is also a checked reason difficulty stays an order and does not become a single number. Collapsing the difficulty classes into a group, the standard group completion, erases everything: regions combine by union, union absorbs repetition, and the completion of such an operation is trivial. Saturating budgets collapse the same way. Only exact resource counts survive the passage, and they are not where hard problems live.

The remaining temptation is a twist: gluing data that no re-choice of components can flatten, as in twisted K-theory. This is checked in both directions. Order-valued fibres force strictness, so nothing non-split was ever possible there, and the split presentation was a theorem rather than a choice. One small example with symmetric fibres carries a genuine twist that cannot be flattened. A twisted theory of difficulty would need fibres that remember more than the order, and coefficients that survive completion.

Relational and real

Information, action, and resource boundaries are relations, but facts inside them can be objective. States either are or are not distinguished by an experiment class. Targets either are or are not in an action closure. Algorithms either do or do not meet a declared bound.

The strongest objectivity comes from invariance across a fixed comparison class. Exact coordinate changes preserve behavior. Complexity results can survive efficient simulations between accepted machine models. Changing the comparison class after seeing the answer proves nothing.

There is no scalar difficulty of a bare problem before the task and encounter are specified. What can be measured are information rates, error tubes, reachable sets, barrier depths, memory, time, queries, and approximation loss. Their attainable regions form realized subposets inside ambient performance fibres. Preimage reindexes the ambient fibres; proved preimage closure, for example through compatible encounter transport, extends this to a fibred order of realized difficulty classes.

Lean verifies the finite and algebraic consequences used by the full book: deterministic report refinement and decision loss, information-budget arithmetic, constant and uniformly switched scalar error recurrences, deterministic fault margins, observation-class intersections and active probing, reachability, barriers, coordinate invariance, abstraction lifting, finite-memory bounds, and optima inside finite program envelopes. On the fibred order itself it now also verifies the total category over comparison contexts with its cartesian lifts and standard fibres, closure operators for the action, information, and behavior boundaries together with their two proved failure cases, and the triviality of group completion for idempotent difficulty classes and for saturating budgets. Verification proves derivability from those hypotheses. It does not prove that the hypotheses are the right model of a physical system.