38
$\begingroup$

The $24$ game is as follows. Four numbers are drawn; the player's objective is to make $24$ from the four numbers using the four basic arithmetic operations (in any order) and parentheses however one pleases.

Consider the following generalization. Given $n+1$ numbers, determine whether the last one can be obtained from the first $n$ using elementary arithmetical operations as above. This problem admits succinct certificates so is in NP.

Is it NP-complete$?$

  • 0
    This sounds pretty similar to subset sum (http://en.wikipedia.org/wiki/Subset_sum_problem), which is NP complete.2010-07-24
  • 8
    Can we *not* use LaTeX if the formula is simple enough like 'n+1'? And $NP$ is definitely wrong — at least use $\mathrm{NP}$.2010-07-24
  • 0
    @Simon: Similar, yes; but can you show a reduction from it?2010-07-24
  • 0
    Not yet, which is why I left a comment rather than an answer.2010-07-24
  • 0
    @Akhil: Looks like we're going to need a hint (I'm assuming you already know the answer.. :)2010-07-25
  • 0
    No, I don't know the answer. I thought there might be a reduction from subset-sum, but didn't see how to do it.2010-07-25
  • 0
    Should all numbers be different? (no, I do not know the result anyway, it's just out of curiosity)2010-07-26
  • 0
    Not necessarily, but if it makes it any easier, that's fine too.2010-07-26
  • 0
    @313 You should only edit such ancient posts if the edit is important. Your edit was far too minor!2014-05-22

3 Answers 3