Elektrine lite

← Feed

@simontatham@hachyderm.io

2026-03-02 12:55 UTC

Pop-science treatments of the P/NP problem often use examples like "If P=NP, then writing a great novel would be just as easy as knowing one when you read it". More generally, searching for a thing meeting some difficult condition would be as easy (in a very loose sense) as checking a candidate thing presented to you as input. In this context, we take it for granted that search is _at least_ as hard as recognition; the only question is whether it's far harder, or whether they're the same. (Surely you can't search for a thing without having some way to know when you find it?) But in some situations, search can be _easier_ than recognition. This happens in cases where the space of acceptable things is particularly large and complicated. It might well be easier to restrict to a subset and reliably produce good things in that subset, than to recognise all the possible good things that _aren't_ in your chosen subset. Purely computational examples: writing a PDF is easier than reading a PDF (a reader must understand the whole spec, but a writer gets to pick and choose). Writing C as program output is easier than consuming it as input (e.g. you can bracket every subexpression to avoid the need to fully understand the parsing rules). Human creative example: code review can be _harder_ than writing code from scratch, because your own particular coding style forms another of those restricted subsets. It's easy to tell that something isn't exactly how _you_ would have done it, but harder to look past that and judge whether it's _good_, separately from your personal stylistic biases. Writing a great program is _easier_ than knowing one when you read it!

Replies (2)