Public Service Announcement

I'd like to share a heuristic for problem solving in mathematics. It is easy to state and apply, and seems very useful, but many students I've talked with or tutored seem either not to have learned to use it, or not to have recognized its role in their thinking.

Here it is:

When attempting to prove a statement, try to find a logically equivalent statement (e.g. the contrapositive) whose hypothesis and conclusion are more 'constructive'.

What do I mean by 'constructive' statements? Ones which assert the existence of objects, preferably small, easy-to-exhibit ones. By constrast, universal statements, often asserting the nonexistence of certain objects, are 'nonconstructive'.

Here's an example:

Claim: A connected metric space with more than one point is uncountable.

If you're familiar with these terms (wiki them), it should be clear that hypothesis and conclusion are both nonconstructive. Thus, try to prove the contrapositive instead:

A countable metric space with more than one point is disconnected.

This way, we start with an enumeration of points and try to construct a separation.

This strategy is related to 'proof by contradiction', but I'm trying to give some sense of when such strategies are likely to succeed. An example from complexity theory, where this heuristic is close to the heart of our existing methodologies:

Karp-Lipton Theorem: If the Polynomial Hierarchy is infinite, then NP does not have polynomial-sized circuits.

This form of the statement gives the 'lesson' that we want to take home: one plausible complexity hypothesis implies a further kind of complexity. But the proof (like most complexity proofs) is constructive, showing how one kind of simplicity (small circuits for NP) implies another (a PH collapse).

Finally, a beloved classic, arguably prophetic of diagonalization: the infinitude of the prime numbers. This time we find a more constructive equivalent statement that is not quite a contrapositive: 'given a finite list of primes, there exists a prime not on the list'. Then we show a simple algorithm to produce such a missing prime (and if you haven't seen this, I strongly encourage you to try.)

NOOOO!!!!!!!!

All good things must end (in polynomially-bounded time, naturally). Today, sadly, brings the announced retirement of one of my favorite blogs, Computational Complexity by Lance Fortnow.

Lance's blog didn't introduce me to the field (that honor goes to my high school graduation present, Papadimitriou's textbook), but it did much to orient me to current research, conceptual trends in complexity, and the culture and institutions behind the theory. Having gone to a small liberal arts college without much in the way of CS theory, this was invaluable.

Lance's four decades of Favorite Theorems in complexity are a great read, and his early posts build complexity literacy with a Complexity Classes of the Week feature. Along the way, of course, we got Lance's perspective on life, love (in a profession rife with geographic insecurity and perceived nerdiness), and truly appalling food.

Thanks Lance! Your posts will be missed.

Update: The blog is back, with frequent guest-poster Bill Gasarch taking over for Lance. Cool!