It is shown that there exist subsets A and B of the real line which are recursively constructible such that A has a nonrecursive Hausdorff dimension and B has a recursive Hausdorff dimension but has a finite, nonrecursive Hausdorff measure. It is also shown that there exists a polynomial-time computable curve on the two-dimensional plane that has a nonrecursive Hausdorff dimension between 1 and 2. Computability of Julia sets of computable functions on the real line is investigated. It is shown (...) that there exists a polynomial-time computable function f on the real line whose Julia set is not recurisvely approximable. (shrink)

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. (shrink)

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. (shrink)

A theory of approximation to measurable sets and measurable functions based on the concepts of recursion theory and discrete complexity theory is developed. The approximation method uses a model of oracle Turing machines, and so the computational complexity may be defined in a natural way. This complexity measure may be viewed as a formulation of the average-case complexity of real functions—in contrast to the more restrictive worst-case complexity. The relationship between these two complexity measures is further studied and compared with (...) the notion of the distribution-free probabilistic computation. The computational complexity of the Lebesgue integral of polynomial-time approximable functions is studied and related to the question “FP = ♯P?”. (shrink)

Ko, K., On the computational complexity of integral equations, Annals of Pure and Applied Logic 58 201–228. The computational complexity of Volterra integral equations of the second kind and of the first kind is investigated. It is proved that if the kernel functions satisfy the Lipschitz condition, then the solutions of Volterra equations of the second kind are polynomial-space computable. If, one the other hand, the kernel functions only satisfy the local Lipschitz condition with the Lipschitz constants growing in an (...) exponential rate, then the solutions could be exponential-time hard. We identify a class of Volterra equations of the first kind that can be converted to Volterra equations of the second kind satisfying the local Lipschitz condition. The complexity of the solutions of these equations is also proved to be exponential-time hard. (shrink)