## Thursday, July 29, 2010

### What is the complexity of these problems and metaproblems?

The following problem is from Doctor Eco's Cyberpuzzles. I have shortened and generalized it.
We are going to put numbers into boxes. If x,y,z are in a box then it CANNOT be the case that x+y=z. If you put the numbers 1,2,...,n into boxes, what is the smallest number of boxes you will need?

(CLARIFICATION ADDED LATER: I mean that x,y,z are ANY three numbers in a box. For example, 10,11, and 21 CANNOT all be in the same box. One of the comments thought they could by letting z=10, x=11, y=21. This is NOT what I intended.)

You can use a simple greedy algorithm to get some partition, but it might not be optimal. The following set is not NPC (by Mahaney's theorem) but also seems to not be in P: I suspect that the following set is not NPC and not in P:

{ (n,k) : there exists a way to partition {1,...,n} into at most k boxes so that no box has x,y,z with x+y=z }

There are many variants.

{ (n,k) : there exists a way to partition {1,...,n} into at most k boxes so that no box has x,y,z with x+y=2z }

This one I know is thought to be hard- it is asking for the min number of colors so that you can color {1,...,n} and not have any Monochromatic arithmetic sequences of length 3. This is an inverse van der Warden numbers; hence I am sure that it is not in P, and that there is no proof of this, and its not NPC.

Let E be a linear equation like x+y-z=0. We represent E by its coefficients., so E would be (1,1,-1). The statement E(a,b,c)=0 means a+b-c=0. Fix E on a fixed number of variables, say a. How hard is

{ (n,k) : there exists a way to partition {1,...,n} into at most k boxes so that no box has x1, ..., xa with E(x1,...,xa)=0 }

If we do not insist the set being partitioned was {1,..,n} we get more problems:

{ (a1,...,an,k,E) : there exists a way to partition {a1,...,an} into at most k boxes so that no box has x1,...,xm with E(x1,...,xm)=0 } I suspect this is NPC.

One can always use the Greedy Algorithm on the above problem, though it may not give the optimal answer. Consider the following meta problems: (the problem'' can either refer to the version where we are partitioning {1,...,n} or a given set. Hence below there are eight problems, not four.)
1. { E : For the problem with E, Greedy gives optimal }. This is in co-NP.
2. { (E,a) : For the problem with E, Greedy gives within a*optimal }. This is in co-NP.
3. { E : the problem with E is in P }
4. { E : the problem with E is NPC }
For the last two I don't even know if they are decidable.

1. { (a1,...,an,k,E) : there exists a way to partition {a1,...,an} into at most k boxes so that no box has x1,...,xm with E(x1,...,xm)=0 } I suspect this is NPC.

why do you suspect this is NPC?

2. It looks like the partition problem where
you want to split a set of numbers into
2 sets with equal sums.

In PARTITION there are only 2 parts but the E depends on n.

In my problem you have k parts but E has
only a fixed number of variables.

The ability to let a_1,...,a_n be whatever you want makes me think that some
trick with coding things into bits might work.

But I don't really know.

3. Maybe it's specified better in the original problem, but there's nothing saying that z has to be the largest number in the box. If box 1 has the numbers 1, 2, and 3, set z == 1. 2 + 3 != 1. This trivializes the problem into ceil(n / 3) boxes. Arguing definitions and going against the spirit of the problem, but I see nothing dictating how the numbers are to be labeled, leaving the choice up to you.

4. Last anon- you seem to be talking about
just one case of the problem.
Do you have a solution, trivial or not,
that will, given n, tell me the MIN number of boxes to place 1,...,n
such that if x,y,z are ANY numbers in a box then x+y NE z ?

5. I don't have one right now, give me some more time to think about it. I wished you had included the statement, "x,y,z are ANY number in the box". Without the any, the solution is trivial. The ANY, implying all combinations of x y and z to the 3 numbers in the box, changes the problem from what you had originally stated. I was thinking of the problem as it was layed out.

If x, y, and z are in a box, then it cannot be that x + y == z. Nowhere in the original statement makes any claims about x,y,z taking all permutations of the numbers in the box and all of those permutations still have to hold to the x + y =/= z. This makes things tougher, but varies in important ways from the question you asked.

If I go with my first reading of the problem, I can give you a solution that will tell you exactly how many boxes you will need. Since the original statement makes no claims to how x, y, and z get assigned, this leaves me to do the assigning. put the first 3 numbers in box 1, with the highest lowest number being tagged as z. Put the next 3 numbers into box 2, with the lowest number tagged as z. Repeat until you are out of numbers. In this scenario, from what I first read of the problem, you will need: [;\left \lceil \frac{n}{3} \right \rceil;]

6. Jason,

1) I have edited the post to
include a clarification.