This work is licensed under a
Creative Commons License.
|
Thursday, July 29, 2010
What is the complexity of these problems and metaproblems?
Posted by GASARCH
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.)For the last two I don't even know if they are decidable.
- { E : For the problem with E, Greedy gives optimal }. This is in co-NP.
- { (E,a) : For the problem with E, Greedy gives within a*optimal }. This is in co-NP.
- { E : the problem with E is in P }
- { E : the problem with E is NPC }
9:50 AM
# 9 comments
-
{ (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
-
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.
-
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.
-
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 ?
-
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;]
-
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.
-
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.
-
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.
-
here is a proof of P=NP, give me some comment http://www.anhphamillusion.co.cc/website/pversusnp.html
Links to this post:
Weblog Home
Archives
