On the complexity of real and complex functions defined on the two-dimensional plane

Computational complexity is a central area of theoretical computer science. Corresponding to the objects being studied, there are two categories: continuous complexity and discrete complexity. Since 1970s, many complexity theories have been developed on discrete computation, and a number of important results, especially those related to the P versus NP problem, have been obtained. On the other hand, although there is significant progress in the continuous side, it is fair to say that, compared with discrete complexity theory, more work could and should be done in continuous complexity theory. For instance, a fundamental issue in continuous complexity theory is the lack of a single, universal computational model that all researchers agree upon. Another major issue is that the computational complexity of many fundamental problems in computational mathematics is not known or not even attacked at all. An example is the computational complexity of analytic continuation problem. The basic computational model we used in this dissertation is the oracle Turing machine model of Ko and Friedman, in which complexity is measured by the number of bit operations needed to output an approximation to the results within the required precision. In this dissertation we study the computational complexity of the following fundamental problems in continuous mathematics. (1) Computing the analytic branches of the logarithm function and the square root function defined on a two-dimensional Jordan domain (Ko and Yu [45]). The key result is as follows: When the boundary of the Jordan domain is polynomial-time computable, then the complexity of computing the analytic branches of the logarithm function is characterized by the complexity class #P. (2) Operations on the NC and log-space functions (Yu [82; 83]). We show that analyticity is critical for the two fundamental operations, integration and differentiation, to be closed in NC or log-space, respectively. We also investigate the problem of finding all zeros of an analytic NC or log-space function inside a Jordan curve. In addition, we discuss the expressive powers of different representations under NC and Log-space. (3) Convex hulls of two-dimensional sets (Ko and Yu [47]). We show that the convex hull of a P-computable Jordan domain S is NP-recognizable but not necessarily polynomial-time recognizable if P ≠ NP. We also show that the area of the convex hull of a P-computable Jordan domain S is computable in polynomial time relative to an oracle function in #P, and the area is a #P real number if NP = UP. (4) Circumscribed rectangles and squares (Yu, Chou and Ko [85]). Our main results are: (a) The minimum-area circumscribed rectangles of a P-computable Jordan curve are not necessarily computable; (b) The complexity of the minimum area of all circumscribed rectangles of a P-computable Jordan curve is characterized by the complexity class SP2 ; and (c) If there exist a unique circumscribed square of a P-computable Jordan curve, it is computable but can be arbitrarily hard. (5) The pancake problem (Yu [84]). We study the complexity of finding a straight line that bisects simultaneously two bounded sets in the two-dimensional plane. We characterize its complexity by the complexity class #P, under some thickness assumption and separability assumption on the sets in question. We have also obtained positive and negative results regarding some related problems such as the problem of bisecting one set in a given direction.