= 27d567bc2d48d9f40e9ccc20ea370b15)
IlyaShpitser comments on What if Strong AI is just not possible? - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (101)
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.