@Jonathan Castello:
> It isn't obvious whether Petri net reachability is in NP at all.

Well, every decision problem in NP [has an exponential-time algorithm](https://cs.stackexchange.com/questions/41555/does-every-problem-in-np-have-an-exponential-time-algorithm). And as John's book explains on p.251, the complexity of reachability is at least doubly exponential. Doesn't this mean that reachability cannot be in NP? *[Edit: I misread the statement in the book, which is about Presburger arithmetic rather than Petri net reachability. So this doesn't really work.]*

Now that we're talking about computational complexity, it may be fun to note that also computational complexity itself is a resource theory! Here, the resources are all the possible decision problems, while we write \$$x \leq y\$$ if the decision problem y can be reduced to x in, say, polynomial time.

It may sound a bit funny that I'm calling the decision problems 'resources', and it's better to think of the resources themselves as being the *oracles* for those decision problems. But technically I find it harder to define what an oracle is, so that's why I've written down the poset of decision problems.

For given decision problems \$$x\$$ and \$$y\$$, we can take \$$x + y\$$ to mean the decision problem that asks you to solve either an instance of \$$x\$$ or an instance of \$$y\$$. So we really have a resource theory as well! It's one that behaves very differently than the one for lemon pie. I won't go into the details now, since I don't know what will be discussed in the upcoming lectures.