Is the $24$ video game NP-complete?

The $24$ video game is as adheres to. 4 numbers are attracted; the gamer's purpose is to make $24$ from the 4 numbers making use of the 4 standard math procedures (in any kind of order) and also parentheses nonetheless one pleases.

Take into consideration the adhering to generalization. Offered $n+1$ numbers, establish whether the last one can be gotten from the first $n$ making use of primary arithmetical procedures as above. This trouble confesses concise certifications so remains in NP.

Is it NP-complete$?$

2019-05-07 02:40:48
Source Share
Answers: 3

There are a couple of nuances that will possibly impact the last solution.

  1. Are we called for to locate the remedy, or just develop presence? By example, establishing if a number has a prime factorization is unimportant, yet locating its prime factorization is hard.

  2. Is the runtime being gauged in regards to a_1, ..., a_n, s or log (a_i), ..., log (a_n), log (s) ? By example, SUBSET - SUM remains in P in the first instance, yet NP - full in the 2nd instance.

2019-05-09 09:08:22

This is still WIP. There are a couple of missing out on information, still I assume it's far better than absolutely nothing. Do not hesitate to modify in the missing out on information.

Offered a trouble of SUBSET-SUM. We have a set of A = a 1 , a 2 , ..., a n numbers, and also an additional number s. The inquiry we're looking for response to is, whether there's a part of A whose amount is s.

I'm thinking that the 24 - video game permits you to make use of sensible numbers. Also if it does not, I assume that it is feasible to mimic sensible numbers approximately of dimension p with integers.

We understand that SUBSET-SUM is NP - full also for integers just. I assume the SUBSET-SUM trouble is NP - tough also if you permit dealing with each a i as an adverse number. That is also if A is of the kind A = a 1 , - a 1 , a 2 , - a 2 , ..., a n , - a n . This is still a crease I require to resolve in this decrease.

Clearly, if there's a part of A with amount s, after that there's a remedy to the 24 - trouble for just how to get to making use of A to s. The remedy is just making use of the + indicator.

The trouble is, what takes place if there's no remedy which just makes use of the + indicator, yet there is a remedy which makes use of various other math procedures.

Allow us take into consideration the adhering to trouble. Allow's take a prime p which is bigger than n, the complete variety of components in A. Offered an oracle which addresses the 24 - trouble, and also a SUBSET-SUM trouble of A = a 1 , a 2 , ..., a n and also s. We'll ask the oracle to address the 24 - trouble on

A = a 1 +(1/p), a 2 +(1/p), ..., a n +(1/p)

for the adhering to values :

s 1 = s+1/p, s 2 = s+2/p, ..., s n = s+n/p.

If the remedy consists of reproduction, we will certainly have a bigger than p ultimately outcome, and also hence we will certainly not have the ability to get to any kind of s i .

Offered an arithmetric expression which contains a i a j = x+(1/p 2 ), It is difficult that the p 2 would certainly "terminate" out, given that there go to the majority of n components in the summation, and also hence the numerator would certainly never ever get to p, given that p>n.

THIS IS NOT QUIT RIGHT! The expression a i a j - a k a l will certainly be an integer, and also consequently our oracle could return solution that includes 2 reproductions one adverse and also one favorable.

What concerning department? Just how can we make certain no department will certainly take place. Locate an additional prime q which is various than p, and also bigger than the biggest a i times n. Multiply all solutions by q. The set A will certainly be

A = qa 1 +(1/p), qa 2 +(1/p), ..., qa n +(1/p)

We will certainly seek the adhering to values :

s 1 = qs+1/p, s 2 = qs+2/p, ..., s n = qs+n/p.

Because instance, a i / a j will certainly be smaller sized than the marginal component in A, and also consequently completion outcome which will certainly has a i / a j will certainly never ever be just one of the s i we're seeking.

2019-05-08 18:13:33

It's worth taking into consideration a couple of means of revealing that the trouble is neither in P, neither NPC. I've noted this solution "area wiki", so please do not hesitate to add pointers and also expand suggestions below.

Based upon my experience playing the 24 video game, it appears that the majority of mixes of numbers are understandable. If we can define this, we can show that the 24 video game is not NPC. Officially, take into consideration the 2^n inputs of size n. If almost polynomially - most of them understandable, after that the language is thin and also can not be NPC (unless P = NP).

2019-05-08 13:57:26