Question

Is there a way to determine if a problem is NP-hard?

Answer 1

The typical method is to demonstrate that you can construct some problem known to be NP-hard using the elements of your engineering problem. But it's important to understand that just because an engineering problem is NP-hard, doesn't mean it has no practical solution. It just means that there is no efficient algorithm that leads to an optimal solution in every case. The important cases might be easy, or a suboptimal solution might be good enough.

Answer 2

There's no trick to easily determine if a problem is NP-hard. Usually you would do so by creating a reduction from your problem to a different problem that is already known to be NP-hard.

Answer 3

Since it seems like your interested in complexity theory. A related topic for optimisation and approximation algorithms is studying NP Optimisation (NPO) classes or some people call it APX, FPTAS, and PTAS. Its an attempt to classify how NP an optimisation problem is.

Answer 4

well yes, of course, otherwise there would be no known np hard problems. I guess you have at least been to the Wikipedia page about np hard and seen an example of one problem listed on there. if there were no methods of showing that a problem is np hard, then we wouldn't say things like "problem X is np hard".