(ADDED LATER- AS STATED the problem below has problems with it. After reading see Eric Allenders comment in the comments.)
Here is a problem whose complexity has probably not been studied. I think it is NP-Intermediary. I will also give a version that is likely NPC. I am proposing that you either prove it is in P or NPC or show that if it is NPC then PH collapses (or something unlikely happens).
DEFINITION: We call a coloring of the x by y grid proper if there are no rectangles with all four corners the same color.
Let L be The set of all (x,y,c) in UNARY such that there is a proper c-coloring of the x by y grid.
- Clearly in NP: verifying that a c-coloring of x by y is proper can be done in time poly in x,y,c.
- Let Lc be the set of all (x,y) such that (x,y,c) ∈ L. Lc has a finite obstruction set and hence is in O(|x|+|y|) thought the constant depends on c. This can be proven by Well-Quasi-Order theory which yields nonconstructive bounds on the size of the obs set, or there is a proof with reasonable O(c2) bounds. (For ALL info on this problem and links to more info see the links below.) Hence the problem is Fixed Parameter Tractable.
- I suspect that the problem L is NP-intermediary. Why? I think its NOT NPC since there is not much to play with- just 3 numbers. I think its not in P because my co-authors and I have not been able to do much more than ad-hoc colorings (this is not that good a reason- however the 17x17 challenge (linked to below) has lead other people to think about the problem and not come up with clean solutions.)
- It is likely that the following is NPC: The set of all (x,y,c,f) where f is a partial c-coloring of the x by y grid such that f can be extended to a proper c-coloring.
- I suspect that whatever is true for rectangles is true if you replace rectangles by other shapes such as a squares. There are also other Ramsey-Theoretic functions that could be studied (though Ramsey's theorem itself not-so-much--- verifying is hard).
- This question is related to the (still unresolved) question I posed here and that Brian Hayes explained better here. However, I don't think proving the general problem NPC will shed light on why determining if (17,17,4) ∈ L is hard. That's just one instance.
...or show that if it is NPC then PH collapses
ReplyDeleteSince this problem (as stated) can be efficiently encoded as a *tally* language (since all three inputs (x,y,c) are in unary), this is a sparse set, and can't be NP-complete unless P=NP by Mahaney's Theorem.
I guess that the interesting question arises if we consider the *binary* encoding of this language. In this setting, the problem is in NE, and the question is: Is it complete for NE? I won't claim to have any intuition about whether it's complete. Probably it's easier to consider the candidate NP-complete problem (where the partial coloring f is also given).
Mahaney's Theorem, right?
ReplyDelete"I think its not in P because my co-authors and I have not been able to do much more than ad-hoc colorings (this is not that good a reason- however the 17x17 challenge (linked to below) has lead other people to think about the problem and not come up with clean solutions.)"
ReplyDeleteIs your point that a 4-coloring of the 17x17 grid is impossible, or that the colorings of maximal grids seems to be difficult to find?
It might be that all the lowest possible upper bounds (on grid size for fixed c) can be proven using a simple counting argument, but that there don't exist any proof that these upper bounds are the lowest possible. In this case the problem would be in P, but we wouldn't be able to prove it. In particular, if this problem is not in P it not only implies that maximal colorings are hard to find, but also that there is no simple reason that larger grid can't be c-colored.
Eric- THANKS for stating the version of my problem that makes sense.
ReplyDeleteSune K. J.- DETERMINIng if 17x17 is
4-colorable seems to be hard. I had many
techniques for showing that a grid was NOT c-colorable but they PROVABLY did not work on 4-coloring 17x17. AND trying to show that 17x17 IS 4-colorable ALSO seems hard as nobody has been able to find it
(of course, it might not exist).