On the complexity of finding paths in a two-dimensional domain I: Shortest paths

摘要

The computational complexity of finding a shortest path in a two-dimensional domain is studied in the Turing machine-based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial-time computable two-dimensional domains: (A) domains with polynomialtime computable boundaries, and (B) polynomial-time recognizable domains with polynomial-time computable distance functions. It is proved that the shortest path problem has the polynomial-space upper bound for domains of both type (A) and type (B); and it has a polynomial-space lower bound for the domains of type (B), and has a #P lower bound for the domains of type (A).