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.

9 comments:

  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?

    I want to know more about this

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

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

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

    ReplyDelete
  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;]

    ReplyDelete
  6. Jason,

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

    2) Reading it your way, you show
    that you can use just n/3 boxes.
    Can you do even better than that?
    I think you can- just put all of
    the numbers in ONE box and always
    assign x,y,z so that x+y\ne z.

    ReplyDelete
  7. The original problem has an easy upper bound of ceil(log_2(n)), just partitioning into groups 2^(k-1)...(2^k)-1, since each pair in the k-th box has a sum at least 2^k. Proving that this is optimal seems harder.

    ReplyDelete
  8. The first problem you ask is equivalent to determining Schur numbers. The number s(t) is the minimum n such that any t-coloring of the positive integers up to n has a monochromatic solution to x+y=z. The problem you ask is essentially the inverse function of s(t). It is known that s(t) is at least exponential in t (the best known exponent follows from blowing up a small case), and at most a constant times t!. Closing the gap is a famous problem in Ramsey theory.

    ReplyDelete
  9. here is a proof of P=NP, give me some comment http://www.anhphamillusion.co.cc/website/pversusnp.html

    ReplyDelete