3 ms·
Far from an expert on complexity theory, but NP-hard problems can be approximated in polynomial time. With Deep Learning you are doing approximation. So this is
by ichbinwiederda 6y ago
Far from an expert on complexity theory, but NP-hard problems can be approximated in polynomial time. With Deep Learning you are doing approximation. So this is nothing ground breaking in that respect.
- Vervious 6y agothere are also a variety of problems that are hard to approximate.
- foxtr0t 6y agoThat actually isn't totally true. Approximate methods, in the formal sense, require a guarantee that they perform within X of the optimal solution. Not all NP-hard problems have polynomial approximations and the methods shown here are likely not approximations because they very likely provide no guarantees on performance. They provide zero guarantees.
- ichbinwiederda 6y agoYes thank you for elaborating. I agree with you on both counts.