Keith wrote:

> So I wondered if reachability is equivalent to satisfiability since satisfiability is well known to be NP-complete.

I will wildly guess that the "satisfiability" you're talking about is [SAT](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem), the Boolean satisfiability problem. This asks whether a Boolean expression like \\( p \vee (q \wedge r) \vee (\neg p \wedge r)\\) is true for some assignment of T and F to all the variables. Reachability, on the other hand, is a question involving Petri nets.

So, they are quite different things. To prove the equivalence you'd wondering about, you'd need to figure out some way to translate reachability questions about Petri nets into satisfiability questions about Boolean expressions.

But I'm pretty sure this is impossible - at least, not in exponential time - because NP problems like SAT can be solved in exponential time, and _nobody knows_ if reachability can be solved in exponential time. We have an exponential _lower bound_ on the runtime of a certain algorithm for reachability, but the best known upper bound is astronomical.

Reachability can, however, be proved equivalent to lots of other questions about Petri nets.

You can see everything I know about this here:

* John Baez and Jacob Biamonte, _[Quantum Techniques for Stochastic Mechanics](https://arxiv.org/abs/1209.3632)_, Section 25.1: The Reachability Problem.

It's really fun stuff.

> So I wondered if reachability is equivalent to satisfiability since satisfiability is well known to be NP-complete.

I will wildly guess that the "satisfiability" you're talking about is [SAT](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem), the Boolean satisfiability problem. This asks whether a Boolean expression like \\( p \vee (q \wedge r) \vee (\neg p \wedge r)\\) is true for some assignment of T and F to all the variables. Reachability, on the other hand, is a question involving Petri nets.

So, they are quite different things. To prove the equivalence you'd wondering about, you'd need to figure out some way to translate reachability questions about Petri nets into satisfiability questions about Boolean expressions.

But I'm pretty sure this is impossible - at least, not in exponential time - because NP problems like SAT can be solved in exponential time, and _nobody knows_ if reachability can be solved in exponential time. We have an exponential _lower bound_ on the runtime of a certain algorithm for reachability, but the best known upper bound is astronomical.

Reachability can, however, be proved equivalent to lots of other questions about Petri nets.

You can see everything I know about this here:

* John Baez and Jacob Biamonte, _[Quantum Techniques for Stochastic Mechanics](https://arxiv.org/abs/1209.3632)_, Section 25.1: The Reachability Problem.

It's really fun stuff.