In Chinese chess, king chasing is a strategy where every move must be a check — you attack the opponent's general continuously until checkmate. This seems like it should be simpler than the full game. You've eliminated most of the move space. No quiet positional play, no long-term planning, no pawn structures. Just check, check, check, checkmate. But deciding whether a king-chasing victory exists on a generalized board is NP-hard, proved by reduction from 3-SAT. The constraint eliminates options but preserves difficulty.
In the prophet inequality, a decision-maker sees random values one at a time and must accept or reject each irrevocably. You can't go back. You can't compare. This seems harder than having full information — and it is, in terms of achievable reward. But the constraint doesn't simplify the computational problem. Under noise, achieving the optimal competitive ratio of 1 - 1/e requires algorithms that simultaneously learn the reward distribution and make stopping decisions. The constraint forces you to act with less information, but the problem of acting optimally remains as hard as ever.
Both cases demonstrate the same phenomenon: constraints that restrict the action space don't necessarily reduce computational complexity.
The intuition that constraints simplify is common and sometimes correct. If you restrict a graph coloring problem to trees, it becomes polynomial. If you restrict integer programming to two variables, it becomes tractable. Structural constraints can cut the problem's complexity by eliminating the hard cases.
But king chasing doesn't cut the hard cases. The 3-SAT reduction works precisely because the forced-check constraint can encode logical variables and clauses. Each check is a choice — which piece checks from which square — and the branching structure of these choices maps onto satisfiability. The constraint makes the game look mechanical (check every move!) but leaves enough branching for NP-hard computation to hide inside.
The prophet inequality preserves difficulty through a different mechanism. The irrevocability constraint doesn't eliminate the hard part of the problem — it relocates it. Without the constraint, the hard part is optimization: given full information, find the maximum. With the constraint, the hard part becomes a learning-optimization hybrid: extract enough information from the sequence to make good stopping decisions without knowing what comes next. The constraint transforms the difficulty rather than reducing it.
The general principle: a constraint reduces difficulty only if it eliminates the source of the difficulty. If the difficulty lies in combinatorial branching and the constraint preserves branching (as in king chasing), complexity survives. If the difficulty lies in information and the constraint removes information (as in the prophet problem), the difficulty transforms into a learning problem that may be equally hard.
This matters for system design. Restricting an agent's action space — fewer choices, stricter rules — is often proposed as a way to make behavior more predictable. But if the underlying decision problem retains its combinatorial structure, the restriction may produce an agent that is constrained without being predictable. King chasing is NP-hard despite being constrained. The constraint didn't buy tractability. It just changed which configurations are reachable, not how hard they are to navigate.