# Time Complexity: Does the following problem belong to NP?

Suppose n people live in a house and wish to share their expenses equally. Their respective expenses (before settling) are x1, ..., xn. They agree to write checks to each other so as to make all their net expenses equal. Naturally, they want to use as few checks as possible.

SETTLEMENT denotes the decision version of this problem: Given nonnegative integers x1, . . . , xn (written in binary) and an integer k, can the net expenses be balanced using k or fewer checks?

I am not sure if I am understanding this problem correctly.. So, given the information, k is a balanced net expense, right? We should find the average net expense of {x1,...,xn}, where x1,...,xn represent the respective expenses. So, SETTLEMENT is as follows:

SETTLEMENT = {(x1,…,xn; k) : there exists some k such that (x1+x2+...+xn) / n = k}.

Your interpretation is incorrect. The value of $$k$$ is not an expense, $$k$$ is the minimum number of checks needed to make sure that the net amount of money paid by each person is $$\overline{x} = \frac{1}{n} =\sum_{i=1}^n x_i$$.
For example if $$n=2$$, $$x_1=1$$, $$x_2=5$$ then $$\overline{x}=3$$ and $$k=1$$. In particular it suffices from the 1st person to write a check to the 2nd person for an amount of $$2$$.
• I think that your algorithm doesn't work. Counterexample: $x_1 = 3$, $x_2=2$, $x_3=1$. Your algorithm uses $2$ checks but only one check is needed. – Steven Apr 9 at 17:55
• That algorithm could prescribe to write checks of negative amounts. Besides, even when this doesn't happen, the algorithm doesn't work. Counterexample: $x_1 = 4$, $x_2 =1$, $x_3=3$, $x_4=0$. Your algorithm writes at least $3$ checks yet the optimal solution uses $2$ checks. In general, I don't think that it is useful for you to guess an algorithm and use me as an oracle to provide you with counterexamples. Try to prove yourself that your algorithm doesn't work. If you consistently fail to do so, then try to write down a formal proof of correctness. Repeat until a solution is found :) – Steven Apr 9 at 18:17