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".
-
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 ignore that and judge whether it's _good_, ignoring your personal stylistic biases.
Writing a great program is _easier_ than knowing one when you read it!
-
R relay@relay.infosec.exchange shared this topic
-
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 ignore that and judge whether it's _good_, ignoring your personal stylistic biases.
Writing a great program is _easier_ than knowing one when you read it!
Very interesting point of view!
-
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 ignore that and judge whether it's _good_, ignoring your personal stylistic biases.
Writing a great program is _easier_ than knowing one when you read it!
@simontatham debunking and verifying bullshit is much harder than writing it in the first place
-
@simontatham debunking and verifying bullshit is much harder than writing it in the first place
@aris ah, yes! That's flipping round the problem conditions in a different dimension. Instead of searching for a particularly _good_ thing, search for a worthless one.
-
@aris ah, yes! That's flipping round the problem conditions in a different dimension. Instead of searching for a particularly _good_ thing, search for a worthless one.
@simontatham think of it like a problem "here is one truth, 99 lies" and you have to figure out which one is the truth. You now have avg 50 problems to solve. Iirc there's a PQC algorithm based on this idea
-
R relay@relay.an.exchange shared this topic
