The computational complexity of distance functions of two-dimensional domains
type: Item
instance of: scholarly article
title: The computational complexity of distance functions of two-dimensional domains
zbMATH Open document ID: 1087.03023
author: Arthur W. Chou
author: Ker-I Ko
published in: Theoretical Computer Science
publication date: 2005-06-30T00:00:00Z
review text: This paper studies the computational complexity of the distance function associated with a polynomial-time computable two-dimensional domain, in the context of the Turing machine-based complexity theory of real functions. Two versions of polynomial-time computability of a bounded two-dimensional domains \(S\subseteq \mathbb{R}^2\) have been introduced: \(S\) is called polynomial-time recognizable if there is a polynomial-time oracle Turing machine \(M\) such that, for any oracles \(\phi_1\) and \(\phi_2\) representing a point \({\mathbf x}\in \mathbb{R}^2\) and any input integer \(n>0\), \(M^{\phi_1, \phi_2}(n)\) correctly determines whether \({\mathbf x} \in S\) for all points \({\mathbf x}\) which have distance at least \(2^{-n}\) from the boundary of \(S\). If, furthermore, \(M^{\phi_1, \phi_2}(n)\) gives correct answers for all \({\mathbf x}\in S\), then \(S\) is called strongly polynomial-time recognizable. This paper shows that, (1) the distance function of \(S\) is not necessarily computable if \(S\) is polynomial-time recognizable; (2) if both \(S\) and its complement \(\overline{S}\) are strongly polynomial-time recognizable, then the distance function is polynomial-time computable if and only if P = NP.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03F60
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 2184062
zbMATH Keywords: computational complexity
zbMATH Keywords: polynomial-time computability
zbMATH Keywords: distance function
zbMATH Keywords: P and NP
reviewed by: Xizhong Zheng
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.11.016
OpenAlex ID: W2017826306
cites work: Computability on subsets of Euclidean space. I: Closed and compact subsets
cites work: Computational Complexity of Two-Dimensional Regions
cites work: On the complexity of finding paths in a two-dimensional domain I: Shortest paths
cites work: Q4942157
cites work: On the definitions of some complexity classes of real numbers
cites work: Q4002474
cites work: Q4249729
cites work: Q3994907
cites work: Q4485693
cites work: Q4787863
DOI: 10.1016/J.TCS.2004.11.016
description: scientific article; zbMATH DE number 2184062