Skip to content

Problem Representation

Version
v1 · 2026-08-24 · History
Prime #
1087
Origin domain
Cognitive Science
Subdomain
problem solving and search → Cognitive Science

Core Idea

The choice of encoding for a problem — its state space, operators, cost function, and goal predicate — fixes which operations and intermediate states are reachable, and therefore which solutions can be found at all, before any solving begins.

How would you explain it like I'm…

Setting Up the Puzzle

If you write numbers as Roman numerals, doing big multiplication is super hard, but with our normal digits it's easy, even though it's the same numbers. How you draw or write a problem changes how hard it is to solve. Picking a good way to set it up before you start can make a tricky problem suddenly simple.

How You Describe It

Before you solve a problem, you first choose a way to describe it: what the pieces are, what moves you're allowed to make, and what counts as done. That choice secretly decides which solutions you can even reach, because some moves only exist in some descriptions. The same problem can be easy one way and almost impossible another, just from how you set it up. So if you're stuck, sometimes the smartest thing isn't to try harder, it's to re-describe the problem in a new way. Changing the description is a different kind of work from solving, and it often matters more.

Encoding Decides Solvability

Problem Representation is the structural fact that the way you encode a problem — your choice of states, allowed operations, costs, and goal — determines which moves exist, which intermediate states you can reach, and therefore which solutions are discoverable at all, before any solving begins. The problem isn't really 'given'; you're given a surface description and must *choose* how to represent it, and that choice fences off part of the solution space because operators that exist in one representation are missing in another. So the same logical problem can be easy under one representation and intractable under another. Crucially, representation is *upstream* of search: no clever heuristic can rescue a representation that simply excludes the solution path. This is why mathematicians switch from polar to Cartesian coordinates, or time domain to frequency domain — re-representing is a distinct intervention from problem-solving.

 

Problem Representation is the pattern by which the choice of internal encoding of a problem fixes which operations are available, which intermediate states are reachable, and therefore which solutions can be found at all — in advance of any solving effort. Five commitments define it. First, the problem itself is not given: what is given is a surface description, and representing it requires choosing a state space, operators, a cost function, and a goal predicate. Second, that choice constrains the reachable region of the solution space, because operators present in one representation are absent in another and states made explicit in one may be unrepresentable in another. Third, reformulation transforms hardness — the same logical problem can be trivial under one representation and intractable under another. Fourth, representation is upstream of search: better heuristics cannot rescue a representation that excludes the solution path. Fifth, representations can be productively swapped — change of basis, taking the dual, encoding constraints as objectives, time domain to frequency domain — each a transform with predictable trade-offs. The skeleton recurs across substrates: mathematicians change coordinates, programmers pick a representation that makes a bug a visible state difference, interface designers decide what is encoded in layout versus color versus text, organizations re-represent reporting lines in a reorg. Stripped of substrate vocabulary: fix a representation before searching; the representation determines what is searchable; so changing it changes what is solvable; so representation work is a distinct intervention from problem-solving work.

Broad Use

  • Mathematics: Changing basis, taking the dual, or moving from time to frequency domain so a hard problem becomes trivial.
  • Software engineering: Data-structure choice (array vs. hash vs. tree) sets which operations are constant- versus linear-time.
  • Machine learning: Feature engineering and representation learning acknowledge that the encoding determines what a learner can detect.
  • Interface design: Spatial layout, colour, and grouping encode information that determines the user's available actions.
  • Organizational design: Functional, matrix, and product structures are representations of who-decides-what, each making different decisions easy.
  • Strategy and policy: Framing an issue as economic, ethical, or technological supplies different operators (subsidy, mandate, R&D).

Clarity

Separates what we're solving from how we've encoded it, so a stuck process can be diagnosed as a representation mismatch rather than a failure of effort.

Manages Complexity

Collapses insight, reformulation, change-of-basis, and reorganization onto one question: what representation am I using, and what would change if I swapped it?

Abstract Reasoning

Representation is upstream of search — better heuristics cannot rescue an encoding that excludes the solution path — so reformulation is itself a tactical move with predictable trade-offs.

Knowledge Transfer

  • Linear algebra → organizations: "Choose a basis aligned with the invariants" becomes "align reporting lines with the decisions that must be taken."
  • Data structures → interface design: Per-operation cost reasoning becomes choosing spatial vs. list vs. graph encodings to make user actions cheap.
  • Feature engineering → policy: "Engineer the representation, not the solver" becomes "decide which variables to make decision-explicit."

Example

The Mutilated Chessboard is intractable when encoded as 62 squares, but re-representing it as a count of colours makes the impossibility a one-line parity argument — representation, not search, decides solvability.

Relationships to Other Abstractions

Local relationship map for Problem RepresentationParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.ProblemRepresentationPRIMEPrime abstraction: Representation — is a kind ofRepresentationPRIMEDomain-specific abstraction: Epiphany — is part ofEpiphanyDOMAINDomain-specific abstraction: Polyhedral Model — presupposesPolyhedral ModelDOMAINDomain-specific abstraction: Quadratic Equation — presupposesQuadraticEquationDOMAINPrime abstraction: Problem Space — presupposesProblem SpacePRIMEDomain-specific abstraction: Birman–Schwinger Principle — is a kind ofBirman–SchwingerPrincipleDOMAINDomain-specific abstraction: Conceptual design — is a kind ofConceptualdesignDOMAINDomain-specific abstraction: Energy modeling — is a kind ofEnergy modelingDOMAINDomain-specific abstraction: Logic Model (Program Evaluation) — is a kind ofLogic Model (Pr…DOMAINDomain-specific abstraction: Threat model — is a kind ofThreat modelDOMAINDomain-specific abstraction: Tunnell's theorem — is a kind ofTunnell'stheoremDOMAINDomain-specific abstraction: Visual reasoning — is a kind ofVisual reasoningDOMAIN

Current abstraction Problem Representation Prime

Parents (1) — more general patterns this builds on

  • Problem Representation is a kind of Representation Prime

    Problem_representation is a specialization of the canonical representation prime, specifically the choice of encoding FOR a problem (state space, operators, cost, goal).

Children (11) — more specific cases that build on this

  • Birman–Schwinger Principle Domain-specific is a kind of Problem Representation

    Problem Representation. The Birman–Schwinger principle is a strict domain instance: it replaces the original perturbed-operator eigenproblem with a resolvent-sandwiched threshold problem whose operator class exposes different proof.

  • Conceptual design Domain-specific is a kind of Problem Representation

    The proposed strict upward parent is prime:problem_representation.

  • Energy modeling Domain-specific is a kind of Problem Representation

    The proposed strict upward parent is prime:problem_representation.

  • Logic Model (Program Evaluation) Domain-specific is a kind of Problem Representation

    Logic Model specializes Problem Representation by organizing a program’s need, intervention, and intended results.

  • Threat model Domain-specific is a kind of Problem Representation

    The proposed strict upward parent is prime:problem_representation.

Hierarchy path (1) — routes to 1 parentless root

Not to Be Confused With

  • Problem Representation is not Problem Space because representation is the act of encoding that fixes which problem space you get, whereas the problem space is the searchable arena that encoding produces.
  • Problem Representation is not Framing because representation changes which operations are available, whereas framing only shifts how unchanged options are perceived.
  • Problem Representation is not Transformation because reformulation is one of its moves, whereas transformation is the general mapping of one structure to another.