tag:blogger.com,1999:blog-3722233.post641606025094710414..comments2023-03-25T10:00:22.914-05:00Comments on Computational Complexity: Cleverness SquaredLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-55764763446153722292009-02-13T10:04:00.000-06:002009-02-13T10:04:00.000-06:00Oops, wrong thread -- will repost.Oops, wrong thread -- will repost.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25168775513072362562009-02-13T10:03:00.000-06:002009-02-13T10:03:00.000-06:00This is surely not a mathematical issue, but I hav...This is surely not a mathematical issue, but I have to take issue with your conception (no pun intended) of a family as a collection of people related by blood. Ruling out the Blums seems really peculiar (one parent + Avrim constitutes a legitimate family by your definition, but not both?). And what of families with adopted children -- admittedly, I know of no examples that apply, but can you say with certainty that you have not included any in your list unknowingly?<BR/><BR/>And for a final bit of flame-bait: From a Christian standpoint, doesn't the Holy Family include Joseph?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83068217284576041872009-02-11T15:15:00.000-06:002009-02-11T15:15:00.000-06:00Wasting time chasing multiple grant streams clearl...Wasting time chasing multiple grant streams clearly detracts from research time. However, the 3-year cycle of having to write grant proposals to justify support enforces a valuable process of re-evaluation of research directions and goals. I don't think of that time spent as a loss for my research - it actually ends up being an integral part of it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84325614624139208442009-02-11T11:44:00.000-06:002009-02-11T11:44:00.000-06:00Yes, it's NP-complete, by reduction from partial L...Yes, it's NP-complete, by reduction from partial Latin square completion. [Charles Colburn, Discrete Applied Math 8(1):25-30, 1984] Siddhartha's comment describes the reduction.<BR/><BR/>(This was also the problem used to show Sudoku is NP=hard.)JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49107743280954662009-02-11T11:27:00.000-06:002009-02-11T11:27:00.000-06:00I feel like funding is less vital to Theoretical C...I feel like funding is less vital to Theoretical CS than most scientific disciplines. If a researcher has a steady job at some university, lack of funding might translate into less pay (bigger incentive to do something else), and not able to attend conferences or support graduate students. However, assuming it isn't research that requires, say, a lot of supercomputer time, the researcher can still do some research.<BR/><BR/>Take in contrast someone who studies some sort of molecular biology. That person really does need lots of lab equipment and personnel even to do the most basic of things.<BR/><BR/>With that said, I'm guessing funding TCS research is a lot cheaper - $1 million in funding supports a lot more TCS researchers than biologists.<BR/><BR/>(I am not a TCS person. I am generally TCS friendly, and feel like I can make lots of armchair conjecture.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18838561833864924612009-02-11T11:18:00.000-06:002009-02-11T11:18:00.000-06:00I just realized that the reduction to factoring do...I just realized that the reduction to factoring doesn't work as stated, you also need another constraint in the same row or column of size (n-k) and the form *(n-k+1)(n-k+2)...n or else it reduces to primality which is of course in P.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18078424437626189982009-02-11T11:12:00.000-06:002009-02-11T11:12:00.000-06:00Don't know about NP-complete but of course it can ...Don't know about NP-complete but of course it can be reduced to a version of factoring by putting one multiplicative constraint box of size 2... but this has the form "is n the product of two integers each less than k" which I'm not convinced is as hard as the standard factoring problem.<BR/><BR/>My intuition is that it is NP-complete, but I don't see an obvious construction either.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87919933737760470942009-02-11T09:49:00.000-06:002009-02-11T09:49:00.000-06:00Probably the NP-complete Subset Sum problem can be...Probably the NP-complete <A>Subset Sum</A> problem can be reduced to it by putting the target sum into a horizontal "+N" box and by constraining the set of possible summands by vertical constraints restricting the possible choices to the set of values in the original subset sum instance. By now I cannot give yet a procedure to construct these constraint boxes though. Maybe somebody else on this forum can.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15391378405497615962009-02-11T09:21:00.000-06:002009-02-11T09:21:00.000-06:00The naive approach is to reduce Ken-ken to Sudoku ...The naive approach is to reduce Ken-ken to Sudoku by imposing the 3x3 square constraints as either +45 or *(9!).<BR/><BR/>This, however, is not working. Take n=16, for instance, and consider the following Latin square.<BR/><BR/>1234 5678 9abc 0def<BR/>2341 6785 abc9 def0<BR/>0def 9abc 5678 1234<BR/>def0 abc9 6785 2341<BR/><BR/>3412 7856 bc9a ef0d<BR/>4123 8567 c9ab f0de<BR/>ef0d bc9a 7856 3412<BR/>f0de c9ab 8567 4123<BR/><BR/>9abc 0def 1234 5678<BR/>abc9 def0 2341 6785<BR/>5678 1234 0def 9abc<BR/>6785 2341 def0 abc9<BR/><BR/>bc9a ef0d 3412 7856<BR/>c9ab f0de 4123 8567<BR/>7856 3412 ef0d bc9a<BR/>8567 4123 f0de c9ab<BR/><BR/>Every 4x4 square has the right sum, but is not a permutation.<BR/><BR/>I guess a similar construction defeats *(9!) as well.Unknownhttps://www.blogger.com/profile/04752384695446260553noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90707814702383425532009-02-11T09:07:00.000-06:002009-02-11T09:07:00.000-06:00NP complete I guess since you don't have to draw b...NP complete I guess since you don't have to draw boxes for arithmetic constraints and even if you did, you could just draw a giant box around the entire grid with 405+Unknownhttps://www.blogger.com/profile/08232757325795175217noreply@blogger.com