New answers tagged np-hard
0
Aryabhata's answer can be fixed up by making use of the fact that we can multiply all the numbers by some large $c$, and then add something small to each one to act like a "presence tag", and then supply some extra numbers that will allow us to get to zero if we could get to $cK$ without them. Specifically, we will use $c=2(n+1)$ and 1 as the presence tag.
...
0
Just to give a heuristic argument, based on practical experience.
Almost all instances, of almost all NP-complete problems, are easy to solve. There are problems where this isn't true, but they are hard to find, and it's hard to be positive you have sound such a class.
This has come up in practice several times when people try to write random problem ...
3
It is NP-hard. Given an instance of your problem, the sum of the integers in the optimal subset $N'$ is at least $B$ (which implies that it must actually be exactly $B$) if and only if the corresponding subset sum instance has answer "yes".
0
There are special cases of convex problems that can be solved in polynomial time, e.g. a convex QP defined over a simplex. In general, however, convex programming is NP-hard. However, NP-hard by no means means unsolvable.
Although theorists would probably cringe at the term, there are NP-hard and what I coin as "NP-harder" problems. What I call an NP-harder ...
3
Oddly enough, I could not find any example of NP-hardness reduction done directly by modeling the problem as a language, and showing that a deterministic Turing Machine cannot decide whether a given instance belongs to that language (I might've messed up with the terminology here)
That's not odd at all: it's because no such proof exists. Anything that can ...
4
The only two methods I've seen are (a) a reduction or (b) direct proof (as in the proof of the Cook-Levin theorem). It is almost universally the case that a reduction is easier than a direct proof. Therefore, I suggest you keep trying to find a reduction, and consider other reduction partners. There are lots and lots of problems known to be NP-complete; ...
Top 50 recent answers are included
