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.
Four exams finished, one left. The last one is algorithms, it should be interesting… i have a fair bit of material to learn.