The reachability problem for vector addition systems with states (VASS) is Ackermann-complete. For every k ≥ 3, a completeness result for the k-dimensional VASS reachability problem is not yet available. It is shown in this paper that the 3-dimensional VASS reachability problem is in Tower, improving upon the current best upper bound F7 established by Leroux and Schmidt in 2019.

This thesis first focuses on the vector addition system. Based on the discussion of the existing work, we propose some new understanding of the reachability problem, which will help future research. Next, we focus on the nondeterministic computation, we will carry out quantitative study of the complexity of nondeterminism. AS far as we know, this is the first of it kind. The main contributions of the thesis are the follows:

• First we summarize the existing work of VAS in the recent 60 years including reachability problem, coverability problem and boundedness problem. Especially for the lower bound of reachability problem, we compare with different techniques, which will help some related ver- ification problems in other models.
• Next for the famous KLMST algorithm, we offer a new understanding of the algorithm, i.e. by the form of decomposition-dimension reduction-decomposition-· · · . In this way we try to build a relationship between the reachability problem for (𝑛 + 1)-dimensional VAS and the reachability problem for 𝑛-dimensional VAS, which we believe will contributes to efforts in the reachability problem for fixed dimension.
• Finally for the abstract presentation of finite state computational objects C-graphs, we introduce the concept of height, which characterizes the maximal number of steps a computational object may engage. Then we give a recursive equality of the number of the C-graphs of height , and prove that its growth rate is non-elementary. This result classifies the worst case branching time complexity.

The structure of nondeterministic computations is extremely complicated. C-graphs are abstract representations of the branching structure of nondeterministic computations. The paper investigates the structure of finite state nondeterministic computations by showing that the complexity of the structure increases non-elementarily while the number of computation steps increases. This is achieved by establishing a recursive equation relating the number of C-graphs of a certain height to the number of C-graphs of smaller height.