# NP-Complete: Prove this Problem is in NP (specific)

I'm trying to prove that this problem is in NP:

Given $n$ dices, there are at least $m$ ways of rolling a given value $y$.

Theoretically I need to argue that there is an efficient verifier for Problem $X$. In other words, describe a verifier such that for any yes instance of $X$, there exists a certificate that the verifier will accept, and for any no instance of $X$, no such certificate exists. The running time of the verifier (and hence the size of the certificate) must be polynomial. Typically, a solution to the given problem is a sufficient certificate.

So in other words, I need to solve this problem algorithmically, correct? Any idea how I could implement this?

• If the algorithm produces $m$ ways of rolling a particular value, then checking that each of these $m$ ways sums to $y$ can certainly be done in polynomial time. May 1, 2016 at 22:12
• And how would I go about actually showing that each of these m ways sums to y can be done in polynomial time? May 1, 2016 at 22:13
• (Maybe I am misunderstanding what you are asking.) Addition is polynomial time. You only need to verify an answer in polynomial time. Also, did you mean to write that there are exactly $m$ ways or at least $m$ ways? May 1, 2016 at 22:23
• @copper.hat at least May 1, 2016 at 23:02