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.
That 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.