Problem Representation¶
Core Idea¶
Problem representation is the structural pattern by which the choice of internal encoding of a problem determines which operations are available, which intermediate states are reachable, and therefore which solutions can be discovered at all — in advance of any solving effort. The defining commitments are five. The problem itself is not given; what is given is some surface description, and representing it requires a choice of state space, operators, cost function, and goal predicate. The choice of representation constrains the reachable region of the solution space, because operators that exist in one representation are unavailable in another, and intermediate states that one representation makes explicit may be implicit or unrepresentable in another. Reformulation transforms problem hardness, so the same logical problem can be easy under one representation and intractable under another. Representation is upstream of search: better heuristics cannot rescue a representation that excludes the solution path. And representation choices can be productively swapped — changing basis, taking the dual, encoding constraints as objectives, viewing the time domain as the frequency domain — each reformulation a transform with predictable trade-offs.
Across substrates this skeleton recurs. Mathematicians solve problems by changing representation: polar to Cartesian, time to frequency, primal to dual. Programmers debug by choosing a representation that makes the bug a visible state difference. Interface designers structure a user's task by deciding which information is encoded in spatial layout, colour, motion, or text, and the user's available operations follow. Organizations re-represent who-reports-to-whom in a reorganization, altering the set of decisions takeable at each level. Educators teach not just facts but representations, because the chosen representation determines what the student can subsequently do. Scientists choose units, axes, and variables, fixing what regularities are visible. Strip the substrate vocabulary and what remains is: before searching for a solution, fix a representation; the representation determines what is searchable; therefore changing the representation changes what is solvable; therefore representation work is a distinct intervention from problem-solving work. The pattern is substrate-independent because state space, operator set, reachable region, and reformulation transform are stated abstractly, with only a mild cognitive lean from the problem-solving framing.
How would you explain it like I'm…
Setting Up the Puzzle
How You Describe It
Encoding Decides Solvability
Structural Signature¶
the chosen encoding (state space, operators, cost, goal predicate) — the reachable region it fixes — the constraints it makes expressible or not — the upstream-of-search priority — the reformulation transform with signature trade-offs
The pattern is present when each of the following holds:
- A chosen encoding. The problem is not given; a surface description is, and representing it requires choosing a state space, an operator set, a cost function, and a goal predicate.
- A reachable region fixed by the encoding. The choice constrains which region of the abstract solution space is traversable: operators available in one representation are absent in another, and states explicit in one are implicit or unrepresentable in another.
- An expressible-constraint set. Each representation makes some constraints trivially enforceable and others nearly impossible to state, so the encoding generates the constraint vocabulary of the problem.
- Upstream-of-search priority. Representation precedes solving: better heuristics cannot rescue a representation that excludes the solution path. A stuck process must be checked for representation mismatch before search is tuned.
- A reformulation transform. Representations can be productively swapped — change of basis, primal-to-dual, time-to-frequency, constraints-as-objectives — each transform a move with signature trade-offs in which operators become trivial and which become hard.
The decisive commitment is that the encoding determines what is searchable, so changing the representation changes what is solvable — making representation work a distinct intervention from problem-solving work. These compose into an encoding-determines-search architecture, with the dual-representation move (hold two, translate between them) more powerful than committing to one.
What It Is Not¶
- Not the problem space.
problem_spaceis the space of states and operators a representation induces; problem representation is the act and choice of encoding that fixes which problem space you get. The representation is upstream; the space is its product. - Not framing.
framingshifts how an unchanged decision is perceived (loss versus gain), altering which preferences activate; problem representation determines which operations are available, altering what the solver can actually do. - Not transformation.
transformationis the general mapping of one structure to another; problem representation is specifically the choice of encoding for a problem, with reformulation transforms as one of its moves. - Not abstraction.
abstractiondiscards detail to expose structure; a representation choice may abstract but is broader — it fixes state space, operators, cost, and goal, not merely what is omitted. - Not a mental model. A
mental_modelis an internal account of how something works; problem representation is the narrower encoding that fixes which operators and reachable states a solver has for a specific problem. - Common misclassification. Diagnosing a representation mismatch as a hard search problem — grinding more compute or tuning heuristics on a stuck process whose real fault is that the encoding makes the solution unreachable.
Broad Use¶
- Cognitive science and AI (origin) — Newell and Simon's problem-space hypothesis; Polya's reformulation heuristics; STRIPS-style explicit state-space encoding; the Tower of Hanoi versus Missionaries-and-Cannibals reformulation studies; "why a diagram is sometimes worth ten thousand words"; representational change in insight problems.
- Mathematics and theoretical CS — change of basis in linear algebra; primal-dual reformulation; integer-versus-linear-programming relaxations; encoding NP-hard problems as SAT; spectral versus time-domain representations.
- Software engineering — data-structure choice (array versus hash versus tree) setting which operations are constant- versus linear-time; MVC versus reactive versus functional state representation; debugging as re-representation to make a bug observable.
- Machine learning — feature engineering and representation learning as explicit acknowledgements that representation determines what a learner can do; embedding choice setting which similarities are detectable; convolutional versus sequence representations of an image.
- Interface design — spatial layout, colour, motion, and grouping encoding information that determines user-available operations; the same data as list, map, graph, or chart, each enabling different actions.
- Organizational design — structure as a representation of who-decides-what, with functional, matrix, and product forms making different decisions easy and others hard; reorganizations as representation transforms.
- Strategy and policy — framing a problem as economic, ethical, or technological supplying different operators (subsidy, mandate, R&D) for the same underlying issue.
Clarity¶
Naming problem representation separates what we're solving from how we've encoded it. Naive problem-solving treats the surface description as the problem; mature problem-solving asks "what would be the best representation?" as a first-class question. The distinction matters because representation-bound failures look like solving failures: the student who cannot solve a word problem may have a representation problem rather than a calculation problem, the engineer who cannot fix a bug may need to log and visualize differently rather than try harder, the organization that cannot make a decision may need to re-represent the choice rather than deliberate more. A second clarifying move is representation-as-constraint-generator: each representation makes some constraints trivially enforceable and others nearly impossible to express, so encoding a route-planning problem as a graph makes connectivity constraints trivial while encoding it as a list of waypoint coordinates makes them invisible. A third is representation versus framing — they overlap but differ. Framing shifts perception of an unchanged decision (loss versus gain framing of the same outcome); problem representation determines what the solver can actually do, which operators exist rather than which preferences activate. A fourth is that representation transforms have signature trade-offs: time-to-frequency makes periodicities trivial and transients obscure, primal-to-dual swaps constraints and variables, functional-to-matrix makes cross-functional work easier and accountability blurred — and these signatures are themselves substrate-independent, making each transform a tactical move with predictable consequences.
Manages Complexity¶
The problem-representation schema compresses an apparently scattered family of phenomena — insight, reformulation, change-of-basis, data-structure choice, framing-shift, reorganization, feature engineering, conceptual change — onto a small set of structural roles: a state space, an operator set, a cost function, a goal predicate, and a transform that swaps between representations. Once the schema is named, otherwise-unrelated problems — the Mutilated Chessboard, the Tower of Hanoi, integer programming, choosing an ML architecture, designing a UI, restructuring a team — collapse onto the same axes, and the analyst's load drops from many substrate-specific tactics to one substrate-independent question: what representation am I using, and what would happen if I changed it? The compression is action-guiding because the same intervention family applies across all of them: enumerate the current representation's commitments, identify what its operators cannot express, propose alternative representations, transform and translate between them, and maintain duals where useful. This turns "find the right way to look at it" — which practitioners across mathematics, engineering, and management describe as the load-bearing move — into an explicit, repeatable procedure rather than a flash of luck.
Abstract Reasoning¶
Treating problem representation as the unit enables several substrate-independent moves. The representation-upstream-of-search argument: better heuristics cannot recover a solution the representation excludes, so diagnosing a stuck process must check representation before tuning search, which is why "step back and rethink" is so often the fix. The reformulation-as-intervention argument: a change of representation is itself a tactical move with predictable trade-offs in which operators become trivial and which become hard, a move mathematicians and physicists make routinely and that organizations and policymakers can make with the same structural reasoning. The constraint-generator argument: representations generate the constraint vocabulary of a problem, so constraints expressible only in one representation drive the choice of representation rather than the reverse. The dual-representation argument: maintaining two representations of the same problem and translating between them (primal-dual, time-frequency, formal-intuitive) is more powerful than committing to one, because each representation has blind spots and the intersection of two is smaller. The representation-mismatch failure mode: when the chosen representation excludes the solution path or makes it astronomically expensive, the result is not a hard problem but a representation mismatch, and the structural diagnosis points to reformulation rather than more search. And the representation-learning argument: in adaptive systems — humans, ML models, organizations — the representation is itself learned, and the capacity to learn good representations is the meta-capacity that sets long-run problem-solving capability.
Knowledge Transfer¶
The role mappings are explicit: the state space maps onto the distinguishable problem-configurations a representation makes available; the operator set onto the moves available between states; the cost function and goal predicate onto the encoding of "better" and "done"; the reachable region onto the subset of the abstract problem space the representation lets the solver traverse; the reformulation transform onto the move that swaps one representation for another with its signature trade-offs; and the dual-representation capacity onto the option of holding and translating between representations with different blind spots. Because these are stated abstractly, both the reasoning vocabulary and the specific transforms transfer, and the ports are concrete. The rules for selecting a basis in linear algebra — orthogonality, alignment with problem invariants, simplification of the operator matrix — port to organizational restructuring as "align reporting lines with the decisions that must be taken." The complexity-cost-per-operation reasoning of data-structure choice ports to interface design as choosing spatial versus list versus graph encodings to make some user operations one-click rather than many-step. The "engineer the representation, not the solver" insight of feature engineering ports to policy as identifying which variables to make decision-explicit. Polya's "consider a related problem you can solve" ports to debugging as "produce a related bug you can reproduce, then bridge to the actual bug." And the Mutilated-Chessboard insight — that representing the board as squares is intractable but representing it as a count of each colour makes the impossibility immediate — ports to organizational deadlock, where "we can't agree" is intractable but "we are over-constrained on a single axis" makes the obstruction visible. A team that re-represents per-service logs as a single cross-service trace so an intermittent bug becomes one observable timing pattern, a mathematician changing basis to diagonalize a matrix so its dynamics become obvious, and a policymaker re-framing inequality as a life-expectancy gradient rather than an income spread are doing the same structural work: change the representation so the problem becomes a single observable state difference, before spending any further effort on search.
Examples¶
Formal/abstract¶
Consider the Mutilated Chessboard problem — the canonical demonstration that representation, not search, decides solvability. The task: an 8×8 board has two diagonally opposite corner squares removed (62 squares remain); can it be tiled by 31 dominoes, each covering two adjacent squares? Under the chosen encoding most people reach for first — the board as a 62-square grid with operators "place a domino on two adjacent empty squares" — the reachable region it fixes is astronomical: the search tree of partial tilings is enormous, and exhaustive search to prove impossibility is intractable by hand. The representation is not wrong, but it makes the solution path practically unreachable; better heuristics for ordering domino placements cannot rescue it, the prime's upstream-of-search point exactly. Now apply a reformulation transform: re-represent the board not as squares but as a count of colours. Each domino, covering two adjacent squares, necessarily covers exactly one white and one black square — a constraint that is trivially expressible in the colour representation and invisible in the bare-grid one (the prime's constraint-generator role). The two removed diagonal corners are the same colour, so the mutilated board has 32 of one colour and 30 of the other. Since every domino consumes one of each, 31 dominoes would need 31 of each colour — impossible with 32/30. The impossibility, intractable under the grid encoding, becomes a one-line parity argument under the colour encoding. The signature trade-off is clean: the colour representation makes the covering-constraint trivial but discards spatial adjacency detail one would need to actually construct a tiling when one exists. The diagnostic the prime forces: a stuck solver should suspect a representation mismatch and seek a reformulation before grinding search.
Mapped back: The square-grid versus colour-count encodings are the chosen representations, the tractable-versus-intractable proof the reachable region each fixes, the one-white-one-black rule the constraint the colour encoding makes expressible, and the parity argument the reformulation transform that converts intractable search into a single observable count.
Applied/industry¶
Consider a data-structure choice in software, alongside the structurally identical case of an organizational reorganization — two genuine domains where the encoding determines what operations are available. In the software case the chosen encoding is how a collection of records is represented: as an unsorted array, a hash table, or a balanced tree. The reachable region it fixes is the set of operations and their costs: membership lookup is \(O(n)\) in the array, \(O(1)\) in the hash table, \(O(\log n)\) in the tree; range queries ("all keys between A and M") are trivial and efficient in the tree, expressible but slow in the array, and not expressible at all in the hash table, which discards ordering — the prime's constraint-generator role made concrete. The encoding is upstream of search: no amount of clever query optimization can make a hash table answer range queries efficiently, because the representation discarded the order the query needs. So choosing the representation is a distinct, prior intervention from optimizing the algorithm that runs over it, and a reformulation transform (re-index the data into a tree) changes which operations are cheap, with the signature trade-off that the tree pays \(O(\log n)\) for point lookups the hash table did in \(O(1)\). The organizational parallel maps role-for-role: a firm's structure is a representation of who-decides-what, and a functional encoding (departments by skill) makes within-discipline decisions trivial but cross-functional product decisions expensive, while a product encoding (cross-functional teams) inverts exactly that — the same constraint that is trivial in one encoding being hard in the other. A reorganization is a reformulation transform with predictable signature trade-offs, not mere reshuffling. An engineer choosing a data structure and an executive choosing an org structure do the same structural work: pick the encoding that makes the operations you need cheap, knowing it makes others expensive, before tuning the process that runs over it.
Mapped back: The array/hash/tree choice (or functional/product structure) is the chosen encoding, the per-operation cost profile the reachable region, range-queryability (or cross-functional decidability) the expressible-constraint set, and re-indexing (or reorganizing) the reformulation transform with its signature trade-offs.
Structural Tensions¶
T1 — Representation versus Search (scopal). The prime's central commitment is that encoding is upstream of solving — better heuristics cannot rescue a representation that excludes the solution path. The failure mode is misdiagnosing a representation mismatch as a hard search problem: grinding more compute, tuning heuristics, or "trying harder" on a stuck process whose real fault is that the chosen encoding makes the solution unreachable. Diagnostic: when a solver is stuck, ask whether the solution is even expressible in the current representation before tuning the search — if no sequence of available operators reaches the goal, the problem is not hard, it is mis-represented, and every additional unit of search effort is spent in a space that does not contain the answer.
T2 — Where Framing Takes Over (scopal). Problem representation determines what the solver can do — which operators exist; framing shifts how an unchanged decision is perceived — which preferences activate (loss versus gain). They overlap but are distinct primes, and confusing them misdirects intervention. The failure mode is treating a genuine operator-availability problem as a framing problem (re-describing the decision when the solver actually lacks the moves to act on it) or vice versa. Diagnostic: ask whether changing the encoding would change the available operations (representation) or only the perception of the same options (framing) — if the set of takeable actions is identical before and after, the issue is framing, and representation work will not expand what can actually be done.
T3 — Reachable Region versus Expressible Constraints (coupling). Each representation simultaneously fixes which states are reachable and which constraints are expressible, and these are coupled: a representation that makes a constraint trivially enforceable may discard the detail another operation needs. The failure mode is choosing an encoding for its reachability while ignoring what it makes inexpressible — picking a hash table for O(1) lookup and discovering range queries are now unrepresentable, or a colour-count encoding that proves impossibility but cannot construct a tiling. Diagnostic: for any candidate representation, enumerate both what its operators make cheap and what constraints it makes impossible to state — optimizing reachability alone silently forfeits expressibility the problem may require downstream.
T4 — Signature Trade-offs of Reformulation (sign/direction). A reformulation transform is not free improvement — it has signature trade-offs: time-to-frequency makes periodicities trivial and transients obscure; primal-to-dual swaps which constraints and variables are explicit; functional-to-product org makes cross-functional work easy and within-discipline coordination hard. The failure mode is reformulating to make the current obstacle trivial while blindly inheriting the new representation's blind spots. Diagnostic: before transforming, ask what becomes hard in the target representation, not just what becomes easy — every reformulation moves difficulty rather than eliminating it, so a transform adopted only for its near-side benefit will resurface the displaced difficulty on the far side.
T5 — Committing to One Representation versus Holding Duals (scalar). Maintaining two representations and translating between them (primal-dual, time-frequency, formal-intuitive) is more powerful than committing to one, because each has blind spots and their intersection is smaller — but holding duals costs the overhead of keeping them synchronized and translating correctly. The failure mode runs both ways: committing prematurely to a single representation and inheriting its full blind spot, or maintaining duals so loosely that they drift out of correspondence and the translation between them silently corrupts. Diagnostic: ask whether the problem's blind spots in one representation are covered by the other and whether the translation is faithful — duals add power only when they genuinely differ in what they obscure and the mapping between them is maintained.
T6 — Fixed Representation versus Learned Representation (temporal). In adaptive systems — humans, ML models, organizations — the representation is itself learned, not given, and the capacity to learn good representations is the meta-capacity setting long-run problem-solving ability. This opens a tension between exploiting the current representation and investing in acquiring a better one. The failure mode is treating a learned representation as fixed ground truth — optimizing within an encoding the system could improve, or conversely churning representations so continuously that no stable encoding accumulates. Diagnostic: ask whether the representation in use is a given to be worked within or a learnable variable worth improving — in adaptive substrates the long-run leverage is often in upgrading the representation itself, a move invisible to any analysis that treats the current encoding as fixed.
Structural–Framed Character¶
Problem representation sits at the structural end of the structural–framed spectrum, just barely in from the pure pole. Its skeleton is abstract — before searching for a solution, fix a state space, operator set, cost function, and goal predicate; the representation determines the reachable region, so changing the representation changes what is solvable, making representation work a distinct intervention from solving. State space, operator set, reachable region, and reformulation transform are stated without reference to any medium, which is why nearly every diagnostic reads structural.
Four of the five point one way. The pattern carries no home vocabulary that must travel with it: changing basis, taking the dual, encoding constraints as objectives, viewing the time domain as frequency — the same reformulation move appears across mathematics, programming, interface design, and organizational restructuring, each told in its own words. It carries no inherent approval or disapproval: a representation is neither good nor bad until you specify the problem, and "the same logical problem can be easy under one representation and intractable under another" is a value-neutral structural fact. Its origin is formal rather than institutional, and invoking it recognizes an encoding choice already upstream of search rather than importing a frame (institutional_origin and import_vs_recognize both 0). The single half-point sits in human_practice_bound: the problem-solving framing leans mildly toward a cognitive agent who represents a problem, since the cleanest cases are reasoners and designers choosing an encoding — though the underlying state-space-and-operators structure is realized in pure search and optimization substrates too. That one mild cognitive lean against four structural diagnostics is exactly the just-structural reading the aggregate of 0.1 records.
Substrate Independence¶
Problem representation is a maximally substrate-independent prime — composite 5 / 5 on the substrate-independence scale. On domain breadth, the encoding-determines-search pattern recurs with the same structural force across cognitive science and AI (its origin — Newell-Simon problem spaces, Polya's reformulation heuristics, STRIPS encoding), mathematics and theoretical CS (change of basis, primal-dual reformulation, encoding NP-hard problems as SAT), software engineering (data-structure choice setting which operations are cheap), machine learning (feature engineering and representation learning), interface design (spatial-versus-list-versus-graph encodings determining user operations), organizational design (functional versus matrix versus product structure), and strategy and policy (framing a problem as economic versus ethical to supply different operators) — a wide span earning a 5 on breadth. On structural abstraction, the skeleton (state space, operator set, cost function, goal predicate, reachable region, reformulation transform) is stated without reference to any medium and is realized in pure search and optimization substrates; the only thing shaving abstraction to a 4 is the mild human-cognitive lean of the problem-solving framing, since the cleanest cases are reasoners and designers choosing an encoding. On transfer evidence, the prime scores a 5: basis-selection rules port to organizational restructuring ("align reporting lines with the decisions that must be taken"), data-structure complexity reasoning ports to interface design, feature-engineering's "engineer the representation" ports to policy, and the Mutilated-Chessboard parity insight ports to organizational deadlock — concrete cross-domain interventions transferring. The clean encoding-determines-search core anchors the composite at 5 despite the mild cognitive lean in abstraction.
- Composite substrate independence — 5 / 5
- Domain breadth — 5 / 5
- Structural abstraction — 4 / 5
- Transfer evidence — 5 / 5
Relationships to Other Primes¶
Parents (1) — more general patterns this builds on
-
Problem Representation is a kind of Representation
problem_representation is a specialization of the canonical representation prime, specifically the choice of encoding FOR a problem (state space, operators, cost, goal). The dossier notes it sits between representation (genus) and problem_space (child).
Children (1) — more specific cases that build on this
-
Problem Space is a kind of Problem Representation
The file + dossier: problem_representation is the upstream CHOICE OF ENCODING that fixes which problem_space you get; problem_space is its PRODUCT (the searchable arena). Reparent problem_space under problem_representation.
Path to root: Problem Representation → Representation → Abstraction
Neighborhood in Abstraction Space¶
Problem Representation sits among the more crowded primes in the catalog (27th percentile for distinctiveness): several abstractions describe nearly the same structure, so a description that fits it will tend to fit its neighbors too — transporting it usually means disambiguating within this family rather than landing on it exactly.
Family — Optimization & Constrained Search (18 primes)
Nearest neighbors
- Problem Space — 0.74
- Embeddability — 0.74
- Backcasting — 0.73
- Constraint — 0.72
- Navigation — 0.72
Computed from structural-signature embeddings · 2026-06-14
Not to Be Confused With¶
The most important confusion — flagged for dedup against this
prime's nearest neighbor — is with problem_space. The two
are close enough to be candidates for merging, and the
relationship is genuinely parent/child. A problem space is the
structured set of states, operators, and goal that a solver
searches through — the arena in which solving happens. Problem
representation is the prior choice of encoding that determines
which problem space you get: pick one representation and you
induce one state space with one operator set; pick another and you
induce a different arena entirely. The representation is upstream;
the problem space is its product. This is why the prime insists
representation is upstream of search — the problem space, and
therefore everything searchable within it, is fixed the moment the
encoding is chosen. The practical payoff of holding them apart is
that the problem-space frame treats the arena as given and asks how
to search it well, while the problem-representation frame asks the
prior question of whether a different arena (a reformulation)
would make the solution trivial. (Phase C will settle whether this
prime is best modeled as the more-general parent of problem_space
or as a child; either way the contrast is the same — representation
is the act of encoding, problem space is the searchable structure
that encoding produces.)
It must also be sharply distinguished from framing, with
which it overlaps because both concern "how a problem is set up."
Framing shifts how an unchanged decision is perceived — the same
outcome described as a loss or a gain — and thereby changes which
preferences and emotional responses activate, without changing the
set of available actions. Problem representation changes which
operations are actually available to the solver — which operators
exist, which intermediate states are reachable. The test is
operational: if changing the description leaves the set of takeable
actions identical, the shift is framing; if it changes what the
solver can do, it is representation. Confusing them misdirects
intervention — re-describing a decision (framing) when the solver
genuinely lacks the moves to act on it (a representation problem),
or restructuring the encoding when the real lever is how the
unchanged options are perceived.
A third confusion is with transformation, because the prime's
reformulation move is a transform. But transformation is the
general operation of mapping one structure to another, of which
representation reformulation is a special case applied to problem
encodings. Problem representation is the broader prime that includes
not just the transform between representations but the initial
choice of encoding, the constraint-vocabulary each representation
generates, and the upstream-of-search priority. Identifying the two
reduces problem representation to its reformulation move alone,
losing the point that even the first representation — before any
transform — already fixes what is solvable.
For a practitioner these distinctions decide where to act. A problem-space frame tunes search within a fixed arena; a framing frame adjusts perception of fixed options; a transformation frame maps between structures. Problem representation's contribution is the prior, often-decisive move: choose or change the encoding so the problem becomes a single observable state difference, before spending any further effort on search — the move none of the neighbors makes central.
Solution Archetypes¶
No catalogued solution archetypes reference this prime yet.