tag:blogger.com,1999:blog-3722233.post6241498675946933350..comments2020-05-22T22:05:47.580-04:00Comments on Computational Complexity: A possible NP-Intermediary ProblemLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-9354828387442516352010-04-28T14:03:00.209-04:002010-04-28T14:03:00.209-04:00Eric- THANKS for stating the version of my problem...Eric- THANKS for stating the version of my problem that makes sense.<br /><br />Sune K. J.- DETERMINIng if 17x17 is<br />4-colorable seems to be hard. I had many<br />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<br />(of course, it might not exist).GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84778500361503004672010-04-28T13:27:24.365-04:002010-04-28T13:27:24.365-04:00"I think its not in P because my co-authors a..."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.)"<br /><br />Is 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? <br />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.Sune Kristian Jakobsennoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24286001822406940852010-04-28T11:26:54.202-04:002010-04-28T11:26:54.202-04:00Mahaney's Theorem, right?Mahaney's Theorem, right?MGhttps://www.blogger.com/profile/14713449682571327855noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4986540323131366792010-04-28T11:26:02.300-04:002010-04-28T11:26:02.300-04:00...or show that if it is NPC then PH collapses
Si...<i>...or show that if it is NPC then PH collapses</i><br /><br />Since 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.<br /><br />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).Eric Allenderhttp://www.cs.rutgers.edu/~allender/noreply@blogger.com