Sorry, an error occurred while loading the content.

## [Computational Complexity] What is the complexity of these problems and metap...

Expand Messages
• 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
Message 1 of 1 , Jul 29, 2010
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?
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.

--
Posted By GASARCH to Computational Complexity at 7/29/2010 09:50:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.