The neural network approach should be able to crush any NP-hard problem into an easy problem for the subset of real world examples, although not for all possible examples.
(Note: I'm speaking vaguley, on the same vague level as your comment. I can be more precise as to what my indications indicate)