Monday, January 10, 2005

A friend posted these links on his site. I thought I'd share, since they're for a good cause. Donate.
Interesting article about why you should donate to the Salvation Army rather than the Red Cross ... I can't make an informed opinion with my little bit of information, so I won't say what's right or wrong, but I'm still going to donate. Won't you? If you're wondering about the validity of the link, just check the domain name.

Also, I usually flat-out hate stuff like this, but: from another friend: "If there is at least one person in your life whom you consider a close friend, and whom you would not have met without the internet, post this sentence in your journal."
Yep. I know. Sappy, infective, and almost clique-type reaction, coupled with a pleasing dopamine-response in the brain, but... oh well.
Near and dear... I have friends in this category as well.

However, there are also several people near and dear that I have neglected in real life ... by simply not mailing a damn letter to them. Here's what can happen: You feel guilty, and more guilty as years go by. They give up contacting you at some point, and move on with their life/lives. They forget about you. You, however, don't forget about them, and it tears at you. Just because you didn't send a damn letter. Go out and get in touch with that friend in Washington, maybe in Brazil, in Maryland, in Anchorage, in Ohio, in Portland, in Singapore. Do it before you regret not doing it sooner or at all.

Now, back to my next set of ramblings.

I just bought some new books on mathematics that will make interesting reads. I'll let you all know if they're any good ... after all, if *I* can read this stuff and learn from it (e.g. the person who takes an average of slightly over 5 hours to complete a 2-hour final exam) then chances are in your favor that you can, too.

For those of you who care, here are some of my somewhat more-favored NP-Complete problems (well - there are many other incredibly interesting problems and much more than those on the page, but these are just a subset of the most well known problems that are primarily housed in mathematics and the storage/interpretation of numbers) taken from an Annotated List of Selected NP-Complete Problems as maintained by Paul E. Dunne, a professor in the Computer Science Department at the University of Liverpool:
Number: 9

Name: Comparative Divisibility [AN4] 3

Input: A (strictly increasing) sequence A=< a1,a2,...,an> and a (strictly increasing) sequence B=< b1,b2,...,bm> of positive integers.

Question: Is there an integer, c, such that Divides(c,A)> Divides(c,B), where Divides(x,Y) (Y being a sequence of positive integers) is the number of elements, y in Y, for which x is an exact divisor of y?

Comments: You may think that this has an obvious fast algorithm, and, indeed the algorithm in question is obvious: what it is not is efficient. Consider: how many bits are needed to store the input data (assuming, without loss of generality, that an>=bm)? How many steps, however, is this `obvious method' taking in the worst-case? It is important to realise that representing integer values in unary is not considered to be a `reasonable' approach (the number 250-1 requires 250 digits in unary but only 50 digits in binary).

Number: 11

Name: Quadratic Diophantine Equations [AN8] 3

Input: Positive integers a, b, and c.

Question: Are there two positive integers x and y such that (a*x*x)+(b*y)=c?

Comments: The comments regarding Problem 9 (Comparative Divisibility) are also pertinent with respect to this problem. Again, there is an `obvious' algorithm that, on the surface, appears to be efficient and is seen not to be so only once one compares the input size (space needed to represent the input data) to the actual computation time in the worst-case.

Number: 53

Name: Quadratic Congruences [AN1] 3

Input: Positive integers a, b, and c.

Question: Is there a positive integer x whose value is less than c and is such that x2==a(mod b), i.e. the remainder when x2 is divided by b is equal to a?

Comments: The comments made with respect Problem 9 and Problem 11 are also relevant with respect to this problem.

Number: 57

Name: Simultaneous incongruences [AN2] 3

Input: A set of n ordered pairs of positive integers {(a1,b1),...,(an,bn)} where ai<=bi for each 1<=i<=n.

Question: Is there a positive integer x such that: for each i, ai does not equal the remainder when dividing x by bi?

Comments: As with most number-theoretic problems, the comments regarding Problems 9, 11, and 53 apply.


School starts in One day !