Chris Maase pointed me to the article Scientists Disappointed by Direction of Financing.
Scientists, who were thrilled when President Obama vowed on his first day to "restore science to its proper place," have veered from excitement to dread as the stimulus bill makes its way through Congress.I don't like the direction either, research funding down quite a bit from the original numbers in the stimulus plan. But I still expect science to get a nice boost from the stimulus. Did any of us guess back in December that the stimulus bill would have any science funding at all?
Steve Quake, a Stanford Bio-engineering professor, takes over as guest columnist on The Wild Side blog on the Times site. Quake's first column talks about the pressures of science funding.
I worry about the "opportunity cost" not only of the ideas not pursued and discoveries not made, but also of the time spent trying to convince very conservative review panels to fund one's research – each minute spent writing or administering grants is a minute that wasn't spent thinking deep thoughts about the frontiers of knowledge.I certainly have had my frustrations with the grant process and a few summers without salary in the past. Nevertheless the competition works well for us and we actually get more risk-taking to stand out from the pack.Could we stimulate more discovery and creativity if more scientists had the security of their own salary and a long-term commitment to a minimal level of research support? Would this encourage risk-taking and lead to an overall improvement in the quality of science?
Finally a new math puzzle, KenKen (Cleverness Squared), in the Times. So is the generalized n×n game NP-complete?
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+
ReplyDeleteThe naive approach is to reduce Ken-ken to Sudoku by imposing the 3x3 square constraints as either +45 or *(9!).
ReplyDeleteThis, however, is not working. Take n=16, for instance, and consider the following Latin square.
1234 5678 9abc 0def
2341 6785 abc9 def0
0def 9abc 5678 1234
def0 abc9 6785 2341
3412 7856 bc9a ef0d
4123 8567 c9ab f0de
ef0d bc9a 7856 3412
f0de c9ab 8567 4123
9abc 0def 1234 5678
abc9 def0 2341 6785
5678 1234 0def 9abc
6785 2341 def0 abc9
bc9a ef0d 3412 7856
c9ab f0de 4123 8567
7856 3412 ef0d bc9a
8567 4123 f0de c9ab
Every 4x4 square has the right sum, but is not a permutation.
I guess a similar construction defeats *(9!) as well.
Probably the NP-complete Subset Sum 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.
ReplyDeleteDon'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.
ReplyDeleteMy intuition is that it is NP-complete, but I don't see an obvious construction either.
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.
ReplyDeleteI 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.
ReplyDeleteTake 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.
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.
(I am not a TCS person. I am generally TCS friendly, and feel like I can make lots of armchair conjecture.)
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.
ReplyDelete(This was also the problem used to show Sudoku is NP=hard.)
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.
ReplyDeleteThis 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?
ReplyDeleteAnd for a final bit of flame-bait: From a Christian standpoint, doesn't the Holy Family include Joseph?
Oops, wrong thread -- will repost.
ReplyDelete