Four shapes of the same question
From the earlier guides you already know that a computational problem is a contract — it says what makes an output correct without saying how to compute it — and that one problem has endlessly many instances. Now we add a second, equally useful lens. Take almost any concrete task and you will notice it can be phrased in four different ways, each asking for a different shape of answer. Hold one running example in mind: a map with towns and roads, and the task "get from town A to town B."
The decision version asks a yes/no question: "is there any route from A to B?" The search version asks you to produce an actual object: "give me a route from A to B (or report there is none)." The optimization version wants the best object by some measure: "give me the shortest route from A to B." The counting version asks for a tally: "how many distinct routes go from A to B?" Same map, four genuinely different jobs — and the answer's very type changes, from one bit, to a route, to a best route, to a number.
Decision and search: a yes, and a witness
A decision problem outputs exactly one bit. Every legal input is stamped either yes or no, splitting all inputs into the yes-instances and the no-instances. Reducing the answer to a single bit feels like throwing information away, and it is — deliberately. That austerity is what lets theory compare how hard different problems are on a common scale, which is the whole foundation of the classes P and NP you will meet later. "Is there a route shorter than 100 km?" is a decision question, and its answer is just yes or no.
A search problem is more demanding: it asks for a witness — a concrete object that proves the answer is yes. Not "is there a route?" but "hand me a route." The witness has a wonderful property: it is usually easy to check. Hand someone a claimed route and they can walk it edge by edge and confirm it really connects A to B. This checkability is the bridge to the idea of a verifier: a short proof you can validate quickly even when finding it was hard. A solved Sudoku is the witness; verifying it is trivial; producing it from blank squares is the work.
Search is at least as hard as decision, and the reason is a one-line argument: if you can find a route, you can certainly answer whether one exists (just see whether your search returned anything). The converse need not hold — knowing a route exists does not, by itself, tell you the route. Yet in practice we often turn a decision oracle into a search procedure by asking decision questions about pieces of the answer: "is there still a route if I forbid this one road?" Removing roads that the answer can survive without, one at a time, eventually leaves a route exposed. That is a real, reusable technique called self-reduction — not a free lunch, but a powerful pattern.
Optimization: not just valid, but best
An optimization problem raises the bar from "a valid solution" to "the best valid solution." It has three parts worth naming every time: the feasible solutions (which candidates are even allowed — here, all routes from A to B), the objective (the number scoring each candidate — total distance), and the direction (minimize or maximize). The answer is a feasible solution whose objective no other feasible solution can beat. It helps to separate the optimal value (the best score, say 42 km) from an optimal solution (a route that achieves it); sometimes you want one, sometimes the other.
Optimization connects back to decision through a clean bridge: every optimization problem has a natural decision version, "is there a feasible solution with objective at most k?" If you can answer that yes/no question quickly for any threshold k, then a short scan over values of k pins down the optimal value — for integer objectives you can even binary-search on k. This bridge is used constantly: it is how a hardness result about the decision version ("this yes/no question has no known fast algorithm") immediately tells you the optimization version is hard too.
Counting: how many, and why it can be the hardest
A counting problem asks for the size of the solution set: not "is there a route?", not "give me one route," but "exactly how many distinct routes are there?" The output is a single number, and it can be astronomically large even when each individual solution is short and easy to describe. Counting the subsets of an n-element set has the tidy answer 2^n; the number of routes in a dense map can explode the same way. Counting matters wherever totals, averages, or probabilities are at stake, since a probability is one count divided by another.
Here is the lesson that surprises newcomers: counting is at least as hard as searching, and often strictly harder. The "at least" direction is easy — if you know the exact count, you know whether it is zero, which answers the decision problem for free. The "strictly harder" direction is the striking part. There are problems where finding one solution is genuinely easy, yet counting all solutions is believed to be intractable. So "just count them" is rarely as innocent as it sounds; the tally hides real computational difficulty, and the size of the answer alone hints at why brute-force listing is hopeless.
A concrete contrast makes the gap vivid. To count solutions on a grid, you usually cannot just enumerate them one by one — there are too many. Instead you exploit structure, often with dynamic programming that adds up partial counts cell by cell without ever listing a single full route. The arithmetic of counting (sums and products of sub-counts) is a recurring engine, and it is a first hint that the way a problem is phrased dictates which design paradigm even has a chance.
A ladder of difficulty, and why the framing matters
Lining the four shapes up reveals a rough ladder of difficulty for one underlying task. Decision sits at the bottom (one bit), search adds the burden of producing a witness, optimization adds the burden of beating every alternative, and counting adds the burden of accounting for all of them at once. The ladder is a guide, not an iron law — for an easy problem like shortest paths, all four rungs are tractable — but it is a reliable instinct: if the decision version is already hard, the richer versions are at least as hard.
- Decision: output one bit — does a feasible solution exist? ("Is there a route from A to B?")
- Search: output a witness — produce one feasible solution, or report none. ("Give me a route.")
- Optimization: output a best witness — a feasible solution with optimal objective. ("Give me the shortest route.")
- Counting: output a number — how many feasible solutions exist. ("How many distinct routes are there?")
Why drill on the framing before touching any technique? Because the shape of the question, not the words around it, decides what a right answer even is — and therefore which design paradigm has a prayer of working. "Find a placement of eight queens with none attacking another" is a search problem you would attack with brute-force enumeration or backtracking; "how many such placements exist?" is a counting problem that needs different machinery; "is the cheapest tour under k?" is a decision problem that may be hard. Pin down the shape first, then choose your tool — the rest of this ladder is, in a sense, a catalogue of tools matched to shapes.