3 ms·
Interesting ideas. How long should it take to create one of these solutions? NP-completeness doesn't care whether the thinker is human or neural-net, and optima
by Kednicma 6y ago
Interesting ideas. How long should it take to create one of these solutions? NP-completeness doesn't care whether the thinker is human or neural-net, and optimality can take exponentially long to find.
Also, what if there simply isn't an optimal solution? Matrix multiplication comes to mind; we think it's quadratic-time, given the asymptotic number of operations that ought to be needed, but all existing algorithms are cubic-time (rounded up), and possibly there isn't a quadratic-time algorithm.