# Is the 24 game NP-complete?

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?

-
This sounds pretty similar to subset sum (en.wikipedia.org/wiki/Subset_sum_problem), which is NP complete. –  Simon Nickerson Jul 24 '10 at 7:18
Can we not use LaTeX if the formula is simple enough like 'n+1'? And $NP$ is definitely wrong — at least use $\mathrm{NP}$. –  KennyTM Jul 24 '10 at 7:38
@Simon: Similar, yes; but can you show a reduction from it? –  BlueRaja - Danny Pflughoeft Jul 24 '10 at 7:47
Not yet, which is why I left a comment rather than an answer. –  Simon Nickerson Jul 24 '10 at 8:37
@Akhil: Looks like we're going to need a hint (I'm assuming you already know the answer.. :) –  BlueRaja - Danny Pflughoeft Jul 25 '10 at 6:19

This is still WIP. There are a few missing details, still I think it's better than nothing. Feel free to edit in the missing details.

Given a problem of SUBSET-SUM. We have a set of A={a1,a2,...,an} numbers, and another number s. The question we're seeking answer to is, whether or not there's a subset of A whose sum is s.

I'm assuming that the 24-game allows you to use rational numbers. Even if it doesn't, I think that it is possible to emulate rational numbers up to denominator of size p with integers.

We know that SUBSET-SUM is NP-complete even for integers only. I think the SUBSET-SUM problem is NP-hard even if you allow treating each ai as a negative number. That is even if A is of the form A={a1,-a1,a2,-a2,...,an,-an}. This is still a wrinkle I need to iron out in this reduction.

Obviously, if there's a subset of A with sum s, then there's a solution to the 24-problem for how to reach using A to s. The solution is only using the + sign.

The problem is, what happens if there's no solution which only uses the + sign, but there is a solution which uses other arithmetic operations.

Let us consider the following problem. Let's take a prime p which is larger than n, the total number of elements in A. Given an oracle which solves the 24-problem, and a SUBSET-SUM problem of A={a1,a2,...,an} and s. We'll ask the oracle to solve the 24-problem on

A={a1+(1/p),a2+(1/p),...,an+(1/p)}

for the following values:

s1=s+1/p,s2=s+2/p,...,sn=s+n/p.

If the solution includes multiplication, we will have a denominator larger than p in the end result, and thus we will not be able to reach any si.

Given an arithmetric expression that contains aiaj=x+(1/p2), It is impossible that the denominator p2 would "cancel" out, since there are at most n elements in the summation, and thus the numerator would never reach p, since p>n.

THIS IS NOT QUIT RIGHT! The expression aiaj-akal will be an integer, and therefor our oracle might return answer which includes two multiplications one negative and one positive.

What about division? How can we be sure no division will occur. Find another prime q which is different than p, and larger than the largest ai times n. Multiply all answers by q. The set A will be

A={qa1+(1/p),qa2+(1/p),...,qan+(1/p)}

We will look for the following values:

s1=qs+1/p,s2=qs+2/p,...,sn=qs+n/p.

In that case, ai/aj will be smaller than the minimal element in A, and therefor the end result which will contains ai/aj will never be one of the si we're looking for.

-
I don't understand your proof - just because our oracle gives a solution using multiplication does not mean there's not also a solution using addition; in the same vein, just because there is a solution to the subset-sum doesn't mean it's the same 24-solution our oracle will give. Is this fact dealt with somehow? (if we change the oracle to give every solution, the reduction is simple: append a bunch of 0's and ask the oracle for all the solutions; then check if one of the solutions is of the form a1 + 0*a2 + a3 + a4 + 0*5 + .... But, that is not the question) –  BlueRaja - Danny Pflughoeft Jul 27 '10 at 18:11
@BlueRaja, If I understood the question correctly, the reduction I need to provide is, given an oracle which solves the 24-problem in polynomial time, show it is possible to solve an NPC problem in polynomial time. This will prove the problem is NP-hard. It is easy to see that if we only allow the use of addition in the 24-problem, then it's parallel to SUBSET-SUM. I'm trying to show we can "force" the 24-problem oracle solver not to use multiplication or division. Is that clearer? –  Elazar Leibovich Jul 27 '10 at 20:30
Oh, I see where the confusion lies: you are assuming that the numbers $a_1, a_2, .., a_n$ given in the problem are restricted to integers, but the oracle which solves the problem is allowed to input rational numbers? Is that correct? –  BlueRaja - Danny Pflughoeft Jul 27 '10 at 21:04
This is an interesting avenue, but I'm not entirely sure about the details. For instance, the first statement about multiplication -- is it possible that sum of the denominators cancel? –  Akhil Mathew Jul 28 '10 at 3:14
Couldn't you cancel a 1/(p^2) term by subtracting another product? –  yatima2975 Jul 28 '10 at 14:34

There are a few subtleties that will probably effect the final answer.

1. Are we required to find the solution, or merely establish existence? By analogy, determining if a number has a prime factorization is trivial, but finding its prime factorization is hard.

2. Is the runtime being measured in terms of {a_1,...,a_n,s} or {log(a_i),...,log(a_n),log(s)}? By analogy, SUBSET-SUM is in P in the first case, but NP-complete in the second case.

-
1. Existence is enough (I wasn't talking about the function problem). 2. The second. Well, actually we have to add $n$ to it (I don't think we should take $\log n$). –  Akhil Mathew Jul 28 '10 at 3:03
@Jeff, SUBSET-SUM is never in P. The kind of problems you can never solve in polynomial time, regardless of the actual numbers given to you is called strongly NP-complete en.wikipedia.org/wiki/Strongly_NP-complete –  Elazar Leibovich Jul 28 '10 at 4:12
Oops, it's Jeremy not Jeff. And BTW Jeremy, this kind of post should be in a comment I think. –  Elazar Leibovich Jul 28 '10 at 4:13
Neither of those questions make sense to me - this is not an algorithm, it's a yes or no question. Of course an answer exists: it's either yes, or no. –  BlueRaja - Danny Pflughoeft Jul 28 '10 at 15:43
@ Elazar: Agreed, but I didn't have enough reputation to leave a comment. –  Jeremy Hurwitz Jul 28 '10 at 21:47

It's worth considering a few ways of showing that the problem is neither in P, nor NPC. I've marked this answer "community wiki", so please feel free to add suggestions and flesh out ideas here.

Based on my experience playing the 24 game, it seems that most combinations of numbers are solvable. If we could formalize this, we could show that the 24 game is not NPC. Formally, consider the 2^n inputs of length n. If all but polynomially-many of them solvable, then the language is sparse and cannot be NPC (unless P=NP).

-