# Proving NP-completeness for a not so cheesy problem

Let's say we have a matrix M[1..B, 1..B] (i.e., a square matrix) and a mouse in the upper left corner (1,1). We also have an integer A, which tells how many pieces of cheese there are in the matrix. The mouse can move from a given positon (i, j) either in the direction (i+1, j) or (i, j+1). When the mouse visits a given position (i,j), it collects all the given cheese immediately, so if it decides to return to an already visited position, it will already be empty. Additionally, the mouse can ONLY reverse/back ONCE when traversing the matrix, because we can assume that this mouse doesn't particularly like to change its mind.

So given all these prerequisites, the question is whether or not it is possible for the mouse to collect exactly A pieces of cheese, starting from the position (1,1) and ending up in the position (B,B)?

There should be a proof that this problem is NP-complete by showing it is in NP and by reducing the NP-complete problem Subset Sum.

For showing it is in NP I was thinking about maybe looping through the whole matrix and counting the total number of cheese and then maybe have some sort of boolean condition to check whether or not the amount of cheese the mouse has collected equals to the total amount of cheese located in the matrix and that this will take polynomial time to do. However, I am not sure this is the right way to do and I am even more unsure of how to reduce Subset Sum to this problem. Thus, I am grateful for your help and advice!

The problem is in $$NP$$ since a certificate is the path itself, which has length at most $$2B-1 + 2 = 2B+1$$.

Given an instance $$\langle S, k\rangle$$ of subset sum where $$S = \{x_1, \dots, x_n\}$$ is a set of integers and $$k$$ is the target value, you can create an instance of your problem by choosing: $$B=n+2$$, $$M = \mbox{diag}(0, x_1, x_2, \dots, x_n, 0)$$, and $$A = k$$.

Clearly any path in $$M$$ that collects $$A$$ pieces of cheese implies the existence of a subset $$S' \subseteq S$$ such that $$\sum_{x_i} x_i = A = k$$.

On the converse notice that, given any $$S' \subseteq S$$ satisfying $$\sum_{x_i} x_i = k$$, it is possible to find a path $$P$$ in $$M$$ with the sought constraints (actually, backtracking is not even required) that traverses $$M[i+1, i+1]$$ if and only if $$x_i \in S'$$. This shows that pieces of cheese collected by $$P$$ are exactly $$k=A$$.

Also notice that your problem can be solved by pseudopolynomial-time dynamic programming algorithm having complexity $$O(A \cdot B^2)$$.

• Thank you for your answer, but I don't really get why B should equal n + 2. Could you please explain that? Nov 19, 2020 at 19:08
• And also, wouldn't it be good to use that one opportunity to backtrack and by doing so changing the initial direction? Nov 19, 2020 at 19:18
• $B=n+2$ so the top-left entry $M[1,1]$ and to bottom-right $M[n+2,n+2]$ of $M$ can be set to $0$ (these entries are traversed by every path). Whether or not backtracking is allowed doesn't matter: if there is a solution to subset sum then there is a path for your problem since you can independently choose which nonzero entries on the diagonal to traverse. This path doesn't require backtracking. If there is a path for your problem then the set of traversed diagonal entries induces a solution for subset-sum. Moreover a non-backtracking path collecting the same amount of cheese always exists. Nov 19, 2020 at 19:31
• Okay, thank you! Nov 19, 2020 at 19:47