@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.

> 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.