Dave Kellam

AHHHHHHHHHH. That’s three years of university. How did that happen? I’m starting to feel old now. And now it’s some drinkee drinkee. Starting with some tasty Guinness, followed by some not-so-tasty-but-oh-so-drunkee Olde English. It’s past noon, it’s never too early.

The formal definition of “NP-Complete” uses reductions, or transformations, of one problem to another. Suppose we want to solve a problem P and we already have an algorithm for another problem Q. Suppose we also have a function T that takes an input x for P and produces T(x), an input for Q such that the correct answer for P on x is yes if and only if the correct answer for Q on T(x) is yes. Then, by composing T and the algorithm for Q, we have an algorithm for P.

Simple. Right?

Four exams finished, one left. The last one is algorithms, it should be interesting… i have a fair bit of material to learn.