Keith - you'll notice I've carefully sidestepped the question of whether the Boolean satisfiability problem can be reduced to the Petri net reachability problem. That's a really interesting question, but I don't know the answer.

> The answer seems "yes" because Petri nets are in a computationally stronger class.

That's an interesting guess but not an a proof.

Above, I only discussed whether the Petri net reachability problem can be reduced to the Boolean satisfiability problem. I don't know the answer to that either, but at least I can say some mildly entertaining things about it!