3 ms·
This isn't true. NP-completeness and Turing-completeness both limit what an AI can reason about, and there's no reason to expect that AGI will spontaneously bre
by Kednicma 6y ago
This isn't true. NP-completeness and Turing-completeness both limit what an AI can reason about, and there's no reason to expect that AGI will spontaneously break those barriers.
To use the meme, an AI won't be smarter than us; it'll be faster at being stupid.
- BMSmnqXAE4yfe1 6y agoI don't see how being smarter than us, or solving any of the problems on the list is an NP hard problem. For example, computers beat humans in chess by a wide margin - nothing NP hard about it.
- Kednicma 6y agoBounded proof search is NP-complete, and you can see this if you imagine transforming a bounded proof search into a satisfiability problem; go from "what, if any, proof starts at these assumptions and reaches these conclusions in less than N steps?" into "what, if any, assignment of Boolean values will encode a proof in O(N) values?" This is precisely what got both Gödel and Nash interested in what would become P vs NP. Computers beating humans at chess is a great example of not being smarter, but being stupid faster. Both humans and computers approach PSPACE-complete problems like chess by approximating their searches and looking at trees of possible moves. We have no special insights into how to consider or evaluate moves; we have psychological profiles on which moves might be connected during practical play but no reason to require people to make such moves, and those profiles are largely limited to "openings", classifying the relatively few initial trees. How do computers beat humans in chess? They do exactly what we do, but faster. This isn't smart, but fast stupid.