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

4 Answers

0 like 0 dislike
0 like 0 dislike
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.
0 like 0 dislike
0 like 0 dislike
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.
0 like 0 dislike
0 like 0 dislike
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.
by
0 like 0 dislike
0 like 0 dislike
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".

Related questions

0 like 0 dislike
0 like 0 dislike
2 answers
a_dalgleish asked Jun 21
Contributing to the right math area, If all areas are equally curious
a_dalgleish asked Jun 21
0 like 0 dislike
0 like 0 dislike
5 answers
BrianDenver7 asked Jun 21
Is there a nice way to recast riemannian geometry in terms of principal bundles?
BrianDenver7 asked Jun 21
0 like 0 dislike
0 like 0 dislike
4 answers
hat_films asked Jun 21
How many AMS 2020 subject classifications to list?
hat_films asked Jun 21
0 like 0 dislike
0 like 0 dislike
14 answers
hiribarren2 asked Jun 21
Topics appropriate to teach high school students
hiribarren2 asked Jun 21
0 like 0 dislike
0 like 0 dislike
2 answers
ConradDubai asked Jun 21
How to “topologize” the fundamental group: a primer
ConradDubai asked Jun 21

24.8k questions

103k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!