Is the $24$ game NP-complete?

Question

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$?$

Answer 1

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={a₁,a₂,...,a_n} 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 a_i as a negative number. That is even if A is of the form A={a₁,-a₁,a₂,-a₂,...,a_n,-a_n}. 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={a₁,a₂,...,a_n} and s. We'll ask the oracle to solve the 24-problem on

A={a₁+(1/p),a₂+(1/p),...,a_n+(1/p)}

for the following values:

s₁=s+1/p,s₂=s+2/p,...,s_n=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 s_i.

Given an arithmetric expression that contains a_ia_j=x+(1/p²), It is impossible that the denominator p² 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 a_ia_j-a_ka_l 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 a_i times n. Multiply all answers by q. The set A will be

A={qa₁+(1/p),qa₂+(1/p),...,qa_n+(1/p)}

We will look for the following values:

s₁=qs+1/p,s₂=qs+2/p,...,s_n=qs+n/p.

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

Answer 2

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.

Answer 3

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).