“Solve an NP problem” is “you are looking for a needle in a haystack, but you will know when you find it.”
“Reverse engineer” is “there is a machine that seems to find needles in haystacks quickly. It has loops of copper wire, and plugs into a wall socket. Can you copy it and build another one?”
It just seems to me that if you are trying to reverse engineer a complicated object of size O(k) bits (which can be a hard problem if k is large, as is the case for a complicated piece of code or the human brain), then the search problem where the object is the solution must have been exponential in k, and so is much much worse.
Exponential search spaces are completely typical for NP problems.
Even many “P problems” have an exponential search space. For instance an n-digit number has exp(n) many potential divisors, but there is a polynomial-in-n-time algorithm to verify primality.
“Reverse engineer” is “there is a machine that seems to find needles in haystacks quickly. It has loops of copper wire, and plugs into a wall socket. Can you copy it and build another one?”
I admit that there are some “reverse-engineering” problems that are easy.
I don’t think that’s true; if you have a physical system sitting in front of you, and you can gather enough data on exactally what it is, you should be able to duplicate it even without understanding it, given enough time and enough engineering skills.
“Reverse-engineer” is an almost perfect metaphor for “solve an NP problem.”
This is not true at all.
“Solve an NP problem” is “you are looking for a needle in a haystack, but you will know when you find it.”
“Reverse engineer” is “there is a machine that seems to find needles in haystacks quickly. It has loops of copper wire, and plugs into a wall socket. Can you copy it and build another one?”
It just seems to me that if you are trying to reverse engineer a complicated object of size O(k) bits (which can be a hard problem if k is large, as is the case for a complicated piece of code or the human brain), then the search problem where the object is the solution must have been exponential in k, and so is much much worse.
Exponential search spaces are completely typical for NP problems.
Even many “P problems” have an exponential search space. For instance an n-digit number has exp(n) many potential divisors, but there is a polynomial-in-n-time algorithm to verify primality.
I admit that there are some “reverse-engineering” problems that are easy.
I don’t think that’s true; if you have a physical system sitting in front of you, and you can gather enough data on exactally what it is, you should be able to duplicate it even without understanding it, given enough time and enough engineering skills.
I have an EE professor friend who is working on making it harder to reverse engineer computer chips.