I was almost a good little grad student and went straight to doing the complexity theory homework after class but instead I visited the lounge and then wandered around Wean trying to find a quiet spot to work and bumped into a poster advertising a talk by Nuel Belnap at 3:30. Went to the talk, of course. Neat stuff. It was about reconciling nondeterminism and the sort of locality required by special relativity without (necessarily, though there is other work that includes it) the full machinery of Minkowski spacetime and so forth. The theory is a collection of axioms on a partial order on events that is thought of as a causality relation. In a single "history", a single space-time, we have a < b if a is in the past light-cone of b. But most generally, a < b if b can occur as an event in the future light-cone of a, and a "history" is a maximal <-directed subset of the set of all possible events. So... yeah. Weird.
Finally got some of the complexity theory done. Problem 3 finished, still thinking about problem 2, but it's harder than I thought. Maybe I'll think of something tomorrow morning.