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 No keywords specified (fix it)
Categories No categories specified
(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

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,682
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

Finding Paths Through Narrow and Wide Trees.Stephen Binns & Bjørn Kjos-Hanssen - 2009 - Journal of Symbolic Logic 74 (1):349-360.
From States of Affairs to a Necessary Being.Joshua Rasmussen - 2010 - Philosophical Studies 148 (2):183 - 200.
Multiple Retrieval Paths and Long-Term Retention.Thomas O. Nelson & Charles C. Hill - 1974 - Journal of Experimental Psychology 103 (1):185.
Paths in Zygmunt Bauman's Social Thought.Keith Tester - 2002 - Thesis Eleven 70 (1):55-71.
Semantic Holism is Seriously False.Gerald J. Massey - 1990 - Studia Logica 49 (1):83 - 86.


Added to PP index

Total views
8 ( #918,391 of 2,349,382 )

Recent downloads (6 months)
1 ( #510,581 of 2,349,382 )

How can I increase my downloads?


My notes