One of the traps into which researchers tend to fall is focusing on the hard cases. This is understandable, since the hard cases are (a) the interesting ones and (b) the publishable ones. However, building an immense theoretical framework that does a bit better than the state of the art on a handful of corner cases while *failing abysmally* on more mundane problems is far from useful. If you’re producing a software tool, the best you can claim is that you’ve produced something very *specialized*.

If you’re trying to build a general model of How Things Work™, though, you’ve merely failed. Failing in an interesting and constructive way is the consolation prize.

Some of you may have heard that a gentleman-and-a-scholar by the name of Vinay Deolalikar has presented a proof that P≠NP. (Briefly, this would show that a large class of problems — NP-Complete — which everyone *thinks* are really hard to solve efficiently really *are* really hard to solve efficiently. Much like Fermat’s last theorem before Wiles and friends came along, this is a result that everyone basically believes but no-one has been able to prove.) Cranks have been “proving” that P≠NP (or, more commonly, that P=NP) for decades, but Deolalikar’s attempt at a proof is of much higher quality — and is being taken seriously by the theoretical computing science community. While this paper presents a novel (and insightful, and likely quite useful) approach to complexity proofs and clearly advances the state of the art in proving things about algorithms, most qualified observers are skeptical that it manages to prove its thesis.

The basic problem, as I’m given to understand it, is that Deolalikar’s approach proves too much. Scott Aaronson notes:

As many others have already said, and as the BBC News piece hints at, the clearest reason for skepticism is (basically) that

Deolalikar hasn’t convincingly explained why his approach doesn’t also prove problems are hard that are already known to be easy. This is the simplest sanity check for any attempted proof of P≠NP: if you’re showing that an NP-complete problem like 3SAT is not in P, then your proof had betterfailfor related problems like 2SAT and XOR-SAT, which are known to be in P. Everyone agrees that, if Deolalikar can’t answer this objection, the proof is toast.

Translating that out of TCS-speak: 2SAT is known to be an easy problem. (Its relative, 3SAT, is a canonical example of an NP-Complete problem.) If Deolalikar’s proof of P≠NP also “proves” that 2SAT is hard, it simply fails.

Shifting gears from computing science to economics, we come across the Keynesian concept of aggregate demand. One of Keynes’s great insights was that people have to actually be able to *buy* goods and services for jobs producing and providing the same to be stable — that is, if aggregate demand (AD) gets too low (such as in a recession), you need to boost it to enable recovery. Some of his more zealous followers decided that AD is *all* that matters, and governments should reply to recessions by printing money and, say, throwing it out of helicopters. As Greg Mankiw puts it:

Changes in aggregate supply (due to, say, high marginal tax rates or adverse incentives associated with unemployment insurance) don’t matter, they argue, because employment is being constrained by the low level of aggregate demand.

If the AD-is-everything model is correct, then commonplace patterns in employment simply won’t exist during downturns — the aggregate demand (potential consumer spending) driving seasonal employment shifts no longer exists. And as you might expect, there’s been a fair bit of sophisticated examination of economic indicators to support and refute this position. But what about something simple, like teenagers getting summer jobs?

Heh.

- A challenge to extreme Keynesians (Greg Mankiw)

[University of Chicago economist Casey Mulligan] points out that there is a regular surge in teenage employment during the summer months because more teenagers are available to work (that is, the supply of their labor has increased). That is no surprise: It is normal supply and demand in action. But if aggregate demand were the main constraint on employment, this increase in supply should not translate into higher employment during deep recessions such as this one. But it does!

So *overall* employment of school-age workers is down from 2006, as you might expect from a recession that’s mostly hit workers without post-secondary credentials. But *seasonal* employment is about the same! Those *summer* jobs aren’t going away. *Demand* for the *goods and services* produced and provided by those summer jobs, one must conclude, is still there. Mankiw again:

Most economists, Keynesians and otherwise, ignore this summer change in employment because we focus on seasonally adjusted data. But as Casey points out, the raw unadjusted data may have something important to teach us.

Casey might want us to take this as evidence against the entire Keynesian worldview. I would not go quite that far, but it surely provides a challenge to extreme Keynesianism.

(Tomorrow, Paul Krugman will explain that this is all Bush 43’s fault.)

**Update:** Bryan Caplan points out that these seasonal employment data are consistent with a non-inflammatory reading of Keynes (that is, one that doesn’t rest solely on AD). He teases further insight from the article:

What we learn from seasonal employment, in short, is that if all workers were like temporary workers, there wouldn’t be much of an unemployment problem. Unfortunately, most workers aren’t like temporary workers, and the unemployment problem is very real.

## 0 Responses to “Try the easy cases first”