Post #2150494

2026-03-02 12:55 UTC

Pop-science treatments of the P/NP problem often use examples like &quot;If P=NP, then writing a great novel would be just as easy as knowing one when you read it&quot;. 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&#39;s far harder, or whether they&#39;re the same. (Surely you can&#39;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&#39;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&#39;s easy to tell that something isn&#39;t exactly how _you_ would have done it, but harder to look past that and judge whether it&#39;s _good_, separately from your personal stylistic biases. Writing a great program is _easier_ than knowing one when you read it!

Replies (3)

@lgsp@social.tchncs.de 2026-03-02 13:26

@simontatham@hachyderm.io Very interesting point of view!

Open ##2298368
@aris@infosec.exchange 2026-03-02 13:56

@simontatham@hachyderm.io debunking and verifying bullshit is much harder than writing it in the first place

Open ##2298369
@stylus@social.afront.org 2026-03-02 15:02

@simontatham@hachyderm.io This reminds me of something I've been thinking about ... We have literally no idea what computers can do. Due to the Busy Beaver question, people have extensively investigated what "extremely short" programs can and can't do. Progress on this problem is extremely hard. Finding BB(6,2) requires fully understanding all turning machines of a particular size "roughly 42 bytes long" (my estimate, may be wildly incorrect!) and the value of BB(6,2) is an open question. (https://en.wikipedia.org/wiki/Busy_beaver#:~:text=current%206%2Dstate%2C%202%2Dsymbol%20best%20contender) By contrast, some have found that the smallest i386 linux program is in the range of 45 bytes (https://www.muppetlabs.com/~breadbox/software/tiny/teensy.html) and it's routine for programs (just the executable file!) to clock in at over 100MB. Given that the sheer number of even 1kB programs dwarfs the number of programs humans will ever try running, it seems likely that there are substantially shorter programs that make "an office suite", "a mastodon client", "a web browser" ... but we have no effective way of finding them. Instead, to borrow your framing, we've chosen a paradoxically much easier "search" method that generates huge programs instead of tiny programs. This also means that there are probably extremely small programs that do surprising things we haven't even conceived of. This reminds me of a quip I've seen attributed to Knuth about the P=?NP problem itself: Given the sheer number of possible programs (exponentially many for any length), it seems statistically likely that at least one of them must solve the problem of interest in polynomial time, therefore P=NP. I've never been sure if this is some kind of meta-joke or is actually a held position... (And of course there's also the famous apology about writing such a long letter: The author simply didn't have enough time to write a short letter on the subject)

Open ##2298373