In verification methods based on Petri nets, the step has been widely applied to the decrease of the interleaving of transition firings. To study the computational complexity of the algorithm for building a reachabilitygraph based on steps, a new decision problem, the step problem, is proposed for Petri nets. The NP-completeness ofthis problem is proved by the reduction from the independent set problem. A polynomial-time algorithm for themaximal step problem is then presented. Furthermore, the maximum step problem is proved to be NP-equivalent.Finally, two kinds of sub-problems solvable in polynomial time are also discussed and analyzed.