1
$\begingroup$

I've learnt about complexity classes but my knowledge doesn't seem to help much when I am given a problem and need to decide it's complexity.

Here is the problem at hand: A set of weights with the same dimensions but with different densities have to be ordered on a plank (on a straight line). The length of the plank is not enough to put everything in one line so you'd have to stack weights on top of each other. There are $n$ weights and there's space only for $m$, $m<n$ weights on the plank. The weight of each object is given.

The target is to stack weights such that the weights are spread across the plank as smoothly as possible. The following figure shows a sample (possible) solution for n=11 weights each having weight w1 to w11 and m=5.

sample solution

The smoothness of the weight distribution is calculated by finding the average of all weights and summing up the deviation from this value at each spot.

Now definitely this is a combinatorial problem. And it is definitely a 'yes' 'no' answerable problem.

It seems to me that it's not in NP. Because given a solution, there is no way of saying in polynomial time that it's the correct answer. Is this right?

If so, does that mean it is in NP hard?

How can I really find which class it belongs to.

I'd appreciate it if anybody could help me with this problem.

$\endgroup$
3
$\begingroup$

You have described an optimization problem, namely, find the arrangement that minimizes the average deviation from the mean. The decision version of this problem is, given an input to your problem and a value $T$, whether there exists an arrangement whose average deviation is at most $T$. This problem is in NP.

Whether it is NP-hard or not is for you to ponder. Combinatorial problems in NP tend to be either NP-hard or in P, so you should simultaneously try to prove that your problem is NP-hard via reduction from a known NP-hard problem, or to find an efficient algorithm for your problem.

$\endgroup$
  • 1
    $\begingroup$ How can one find an efficient algorithm for a problem like this? By try&error or by searching for known similar problems? $\endgroup$ – undefined Jul 3 '18 at 11:15
  • 2
    $\begingroup$ There is no silver bullet for problem solving. $\endgroup$ – Yuval Filmus Jul 3 '18 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.