## [Computational Complexity] A possible NP-Intermediary Problem

Expand Messages
• (REMINDERS: STOC Early Registration closes on April 30. CCC Early Registration closes May 3. EC Early Registration closes on May 6. ) Here is a problem whose
Message 1 of 1 , Apr 28, 2010
• 0 Attachment
(REMINDERS: STOC Early Registration closes on April 30. CCC Early Registration closes May 3. EC Early Registration closes on May 6. )

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 orshow 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.
1. Clearly in NP: verifying that a c-coloring of x by y is proper can be done in time poly in x,y,c.
2. 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.
3. 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.)
4. 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.
5. 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).
6. 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.

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