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

Mathematical Logic Quarterly 50 (6):551-572 (2004)

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: domains with polynomialtime computable boundaries, and 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 and type ; and it has a polynomial-space lower bound for the domains of type , and has a #P lower bound for the domains of type
Keywords computational complexity  polynmial space  polynomial time  Shortest path
Categories (categorize this paper)
DOI 10.1002/malq.200310120
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 45,328
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
On the Complexity of the Pancake Problem.Fuxiang Yu - 2007 - Mathematical Logic Quarterly 53 (4):532-546.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.
Effective Fractal Dimensions.Jack H. Lutz - 2005 - Mathematical Logic Quarterly 51 (1):62-72.
Tractable Competence.Marcello Frixione - 2001 - Minds and Machines 11 (3):379-397.
Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
An Incomplete Set of Shortest Descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.
On the Complexity of Gödel's Proof Predicate.Yijia Chen & Jörg Flum - 2010 - Journal of Symbolic Logic 75 (1):239-254.


Added to PP index

Total views
30 ( #300,239 of 2,280,259 )

Recent downloads (6 months)
5 ( #238,437 of 2,280,259 )

How can I increase my downloads?


My notes

Sign in to use this feature