0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – copper.hat
    May 1, 2016 at 22:12
  • $\begingroup$ And how would I go about actually showing that each of these m ways sums to y can be done in polynomial time? $\endgroup$
    – Carlo
    May 1, 2016 at 22:13
  • $\begingroup$ (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? $\endgroup$
    – copper.hat
    May 1, 2016 at 22:23
  • $\begingroup$ @copper.hat at least $\endgroup$
    – Carlo
    May 1, 2016 at 23:02

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .