Why Problems Are Hard

The Fibred Order of Difficulty

The same target can be reachable with one actuator and impossible with another. The same state can be recoverable through one sensor and invisible through another. A short proof can exist even when finding it takes extensive work. A difficulty claim becomes informative when it identifies the achievement, the conditions, and the obstruction.

An encounter specifies a task situation: its object, success condition, environment, available information, actions, admitted methods, and charged resources. Its successful attainable region records the performance bounds under which the task can be achieved. The region can have several dimensions, such as time, energy, memory, and error. Different encounters may have crossing tradeoffs rather than one defensible ranking.

The book's philosophical commitment is to objective constraints within justified encounters. The ends can be chosen while what achieves them remains a matter of fact. Its further suggestion that those constraints express dispositions is a metaphysical conjecture. The book explains what that interpretation might add and where the argument remains open.

Success must survive the measurement

Suppose a delivery task requires handing a parcel to its authorized recipient. Two systems each have one routine that takes one minute and causes no damage. One reaches the recipient; the other can reach only a different person. Their recorded time-and-damage performance is identical. Their ability to complete the task is not.

This is why the book distinguishes two regions. The full performance region includes bounds achieved by any admitted method, including unsuccessful ones. The successful region includes only bounds achieved by methods satisfying the fixed success condition. The second region is empty for the misdirected delivery system. The first conceals the problem if delivery correctness is omitted from its coordinates.

Task difficulty is compared through successful regions. Full regions are useful when studying approximation or graded failure, but a claim about task success must retain the corresponding criterion. Giving a failed method a generous loss allowance does not make it satisfy an unchanged task. If the success threshold changes, the encounter changes with it.

Information, action, and resources constrain different things

A warehouse robot must choose between two corridors. In one layout the left corridor is blocked; in the other, the right. Its camera gives the same report in both. If it must choose immediately, no first turn is safe in every compatible layout. A sensor that identifies the layout makes a safe choice possible. If a closed common door instead blocks both routes, identifying the layout cannot create a path.

Information also has a rate. Under a specified source and observation model, data processing limits how much information about an unknown can enter a maintained representation. Translating that limit into required observations needs a task-relevant loss and an information budget. It is not a theorem that thinking cannot yield knowledge or that every noisy sensor has the same capacity.

An observer may converge in its design model yet lose its guarantee under disturbance or mismatch. A contraction argument can certify an error tube. The tube is an upper guarantee; without another argument it is not a floor on achievable accuracy. Losing that certificate does not establish divergence or impossibility for every observer.

A complete map can shorten search without adding a missing action. A lemma can abbreviate an existing derivation without enlarging what the calculus proves. These changes can still alter finite-budget accessibility. Time spent finding a path, the cost of traversing it, and whether any path exists are separate questions.

An abstraction carries similar obligations. Mapping concrete paths into abstract paths does not ensure that an abstract plan can be executed. Its steps must lift from the concrete state actually reached, and its success test must imply the required concrete success. Safety, cost, and robustness require their own preservation arguments.

What the fibred order contributes

Within a fixed task and comparison context, one encounter is at least as hard as another when its successful attainable region is contained in the other's. Every budget permitting success in the first then permits success in the second. Equal regions mean equivalence for those recorded bounds; they can conceal different mechanisms or discovery histories. If neither region contains the other, an overall ranking needs an additional tradeoff rule.

For a robot, a safe camera package can be slower but use less energy and memory than a safe lidar package. Neither dominates the other. A faster camera package that permits collisions is excluded from the successful region of a collision-free docking task. It can enter a graded-performance comparison only when that different question is made explicit.

Comparisons across performance spaces need more than ordinary local inclusion. A simulator might report motion steps and planner nodes while hardware reports seconds, energy, and memory. First establish that their tasks, admitted worlds, actions, and success conditions are related appropriately. A conversion between units cannot repair an unexecutable simulator move or a missing failure mode.

Under a declared calibration, take all hardware bounds that translate into an acceptable simulator bound. This inverse-image operation transports a specification. If the translation forgets energy, that specification can admit a zero-energy point even when every successful hardware run consumes energy. No hardware encounter in that family realizes exactly the translated region.

The fibred order organizes these local regions and their translations. Semantic alignment, performance calibration, and realization of a translated specification are separate achievements. The mathematics uses established order and category theory. Its value here is to expose obligations that a comparison might otherwise leave implicit.

Finding a method is part of an encounter too

Imagine N labeled candidates, exactly one marked. A deterministic procedure knows only that promise. It can ask whether a chosen label is marked, at one unit per query. Success requires a label accompanied by an affirmative oracle response; guessing or inferring the last label without querying it is not an accepted certificate.

Searching sequentially takes at most N queries. In the worst case, the first N minus one distinct queries all return no. The remaining label is marked, but obtaining its required affirmative response takes the final query. Every successful procedure therefore needs N queries in the worst case.

If the correct label is supplied as advice, obtaining its affirmative response takes exactly one query. Every instance thus has a certificate that is cheap to obtain once the right label is known, while an uninformed procedure faces a discovery cost that grows with N. The same procedure must work for every marked label; giving each instance its own informed procedure changes the question.

This example places discovery inside the framework by declaring initial knowledge, admissible inquiries, success, and cost. It does not explain all mathematical insight. The candidate language and query interface were supplied. Studying their acquisition requires a further encounter that charges for it. There is no universal measure of creativity or experienced effort in these definitions.

What could bear a disposition?

A task situation, its specification, and its performance region are different things. The robot interacting with a warehouse under a docking requirement is a task situation. A tuple recording its components is a specification. A region of resource bounds is a more selective representation. The tuple does not acquire physical powers merely because it represents a machine.

The proposed dispositional interpretation attributes modal resistance to the task situation: its organization constrains successful interaction, including interactions never attempted. This vocabulary connects particular failures with persistent features of the situation. A camera's inability to distinguish layouts is not created by the operator's pessimism.

That gives a reason to consider dispositional language, but does not establish an irreducible power. A rival account can accept the same organization, laws, and counterfactual constraints while treating the disposition as a derivative description. The mathematical results do not decide between these accounts. Following the philosophical discussions of Mumford and Vetter requires an argument about what explains possibilities, not just a new name for the declared possibilities.

The extension to abstract tasks needs additional care. An impossible equation is not thereby a physical object exercising resistance. Formal proof constraints can be objective without settling whether abstract objects have dispositions. The book commits to the constraints supported by the specified model and its interpretation; the stronger metaphysical account remains a conjecture.

Two obstacles can conceal each other

Return to the robot whose camera cannot distinguish the layouts, and also close a common door across both routes. No alternative route or further probing is allowed. Success requires one policy that reaches the dock safely in either layout.

Replacing the camera while keeping the door closed does not restore success. Opening the door while keeping the ambiguous camera also fails to restore the guarantee: each layout now has a path, but the robot still cannot choose a turn safe in both. Opening the door and identifying the layout together restore success.

The door explains why no physical path exists in the original situation. The ambiguous camera explains a different fact: why, with the door open, the existence of a path in each layout does not supply one safe policy. Removing one obstacle without changing the final verdict therefore does not establish that the obstacle was irrelevant. Another restriction can conceal its contribution at that outcome level.

An explanation must identify its target and contrast. Deriving a bound from a premise, or observing stability across several models, does not by itself establish that premise as a metaphysical ground. The overlap example supplies an explanatory analysis of the stated restrictions. It does not turn intervention into a universal definition of grounding.

When reasonable specifications disagree

Consider two safe controller packages. A fast package takes one minute in ordinary conditions and five in a rare mode. A steady package always takes two minutes. The rare mode occurs with probability one in a hundred in the declared distribution. All other charged costs are equal.

A routine-throughput task requires expected time at most one and a half minutes. The fast package's expected time is 1.04 minutes, so it succeeds; the steady package fails. An emergency task instead requires completion within three minutes in every admitted mode. The steady package succeeds; the fast package fails.

Both calculations can be correct descriptions of the same packages. Their success conditions differ. Whether the rare mode occurs, how long delivery takes, and whether the distribution represents deployment are empirical questions. Whether occasional delay is acceptable for the actual service is a question about its ends and consequences.

If the commission requires a three-minute guarantee, the average-time certificate is insufficient. That follows from the commission before inspecting which package benefits. If the commission concerns expected throughput, the average comparison may be appropriate. If the commission itself is disputed, arithmetic alone cannot resolve the choice. Evidence about consequences and reasons from affected parties matter.

The audit helps locate the disagreement and reject a certificate answering the wrong question. It does not decide every ethical tradeoff. Explicit assumptions make a calculation inspectable; they do not automatically justify its application.

When the system reacts to its model

A forecast can change the outcome being forecast without anyone trying to deceive it. Suppose a system announces a number between zero and one. One environment always returns one; another returns one minus the announcement. At an initial announcement of zero, both return one, so that observation does not distinguish them.

Fitting the observation suggests announcing one. That is perfect for the frozen law and maximally wrong for the reactive law. Each law alone nevertheless permits perfect prediction: announce one for the frozen law and one half for the reactive law. If a single announcement must serve against both, the smallest worst-case absolute error is one third, achieved by announcing two thirds.

Reaction changes the required policy; uncertainty about the law imposes the positive robust loss. One policy must work against every admitted response. Choosing a different policy after discovering the response would alter the encounter. Comparing alternative policies must also account for the different histories and responses those policies would generate.

A failed method is not a lower bound

A two-equation example in the full book has a parameter that can be zero. Substitution always solves it at a declared cost of one operation. A more expensive elimination recipe divides by the parameter and fails at zero. The available method set changes there, but the cheapest admitted solution remains available at the same cost.

Contrast the task of finding x such that t times x equals one. For nonzero t, a reciprocal works. At zero, no real solution exists. Both examples contain a division that fails at zero; only the second loses feasibility.

Method stability, optimal certificate cost, discovery cost, and task feasibility must therefore be examined separately. Under the book's strict-ball definition, the supremum of stable radii is itself stable, even when a point exactly on the ball's boundary has a different method set. These statements concern the declared methods, cost, and proximity relation.

A better sensor can guarantee nothing more

Return to the robot and its two corridors, and offer it two sensors. The first names the blocked corridor correctly two times in three, whichever corridor it is. The second is always right when the left corridor is blocked, but when the right corridor is blocked it answers at random. When both layouts are equally likely, the second sensor leads the robot to the open corridor three times in four, the first only two times in three. In the classical comparison of experiments due to Blackwell, the second sensor is strictly more informative.

Now require a guarantee instead: one policy that reaches the open corridor with a stated probability in both layouts. The two sensors support exactly the same guarantees, up to two in three and no further. For that commission, paying for the second sensor buys nothing. If the commission is average throughput, it buys a real improvement. The arithmetic is the same in both cases; the success condition decides which number answers the question.

The book's quantifier, one policy that must succeed in every admitted world, therefore induces its own order on noisy sensors. One sensor is at least as good as another when every task that must succeed everywhere can be guaranteed at least as well. This order is coarser than Blackwell's, and it is a different order: with three worlds, a sensor that is not more informative in Blackwell's sense can still guarantee strictly more. When either sensor is noiseless, the two orders agree, which is why the book's comparison of deterministic reports needs no change.

Three further facts make this order a subject of its own. First, the tasks needed to compare two sensors are known exactly. A task that splits into two independent choices, one within each of two groups of worlds, is only as demanding as the harder of its parts, so it never needs testing separately. Every other task is indispensable. With four worlds, 110 of the 113 tasks in normal form are needed; with five, 6828 of 6893; and the number grows far faster than exponentially.

Second, deciding the comparison is hard, even when every probability is a simple fraction whose size grows only polynomially with the number of worlds. It is coNP-complete, whereas Blackwell's comparison can be decided efficiently. A failure of dominance has a short certificate: one task, one policy, and one least favorable distribution over the worlds. Dominance in general has none unless NP equals coNP. The same pair of a policy and a distribution also assigns blame for a failure: the policy shows what the sensor permits, and the distribution shows what no policy using it can exceed.

Third, the order changes with the required level of success, and not monotonically. Below one over the number of worlds every sensor matches every other; at certainty only which worlds each signal can come from matters; in between, one explicit pair of sensors matches at low levels, fails at intermediate ones, and matches again near certainty.

What is established, and how far it travels

The Lean companion checks the existing algebraic core, including information refinement, reconstruction and fault bounds, reachability, abstraction, finite-memory constraints, region orders, proof-cost laws, and the earlier forecast, calibration, and algebraic examples. The companion also includes a formal layer for the comparison of noisy sensors: the certificate inequality for guarantees, that post-processing a sensor never raises a guarantee, the support rule for certain success, the two-sensor and three-world examples, and the reduction of split tasks to their parts. The full book retains eighteen source disclosures.

The general theorems about noisy sensors, that split tasks are the only redundant tests and that the comparison is coNP-complete, are proved in prose and checked by exact certificates and independent referees. They are not presented as Lean results. The parcel counterexample, discovery-query bound, overlapping-obstacle analysis, and competing service specifications are likewise arguments in prose. Neither their arithmetic nor the existing formal proofs establishes empirical calibration, ethical relevance, or dispositional realism.

When a claim survives justified changes of representation or encounter, its demonstrated scope broadens. Its empirical support does not automatically increase: several models can preserve the same error. A local impossibility can already be objective even though adding an actuator makes success possible in a different encounter.

The resulting discipline is to state success, identify the admitted possibilities, charge for acquisition as well as execution when relevant, establish the obstruction, and justify each comparison. An account of why something is hard must keep the task, the explanation, and the evidence connected.