The computational complexity of distance functions of two-dimensional domains (Q557838)

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.