The polynomial topological complexity of Fatou-Julia sets

We analyze the polynomial topological complexity of Fatou-Julia sets, and show that for Sullivan domains of such sets the complexity is equal to 1 in the case of attracting, superattracting and Siegel domains, while for parabolic domains it is greater than 1.     

Representation theorems for transfinite computability and definability

 We show how Kreisel's representation theorem for sets in the analytical hierarchy can be generalized to sets defined by positive induction and use this to estimate the complexity of constructions in the theory of domains with totality. Received: 21 January 1998 / Published online: 2 September 2002     

Numerical conformal mapping based on the generalised conjugation operator

An iterative procedure for numerical conformal mapping is presented which imposes no restriction on the boundary complexity. The formulation involves two analytically equivalent boundary integral equations established by applying the conjugation operator to the real and the imaginary parts of an analytical function. The conventional approach is to use only one and ignore the other equation. However, the discrete version of the operator using the boundary element method (BEM) leads to two non-equivalent sets of linear equations forming an over-determined system. The generalised conjugation operator is introduced so that both sets of equations can be utilised and their least-square solution determined without any additional computational cost, a strategy largely responsible for the stability and efficiency of the proposed method. Numerical tests on various samples including problems with cracked domains suggest global convergence, although this cannot be proved theoretically. The computational efficiency appears significantly higher than that reported earlier by other investigators.

     

Tutte sets in graphs II: The complexity of finding maximum Tutte sets

A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency. A subset X of V(G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. We explored the structural aspects of Tutte sets in another paper. Here, we consider the algorithmic complexity of finding Tutte sets in a graph. We first give two polynomial algorithms for finding a maximal Tutte set. We then consider the complexity of finding a maximum Tutte set, and show it is NP-hard for general graphs, as well as for several interesting restricted classes such as planar graphs. By contrast, we show we can find maximum Tutte sets in polynomial time for graphs of level 0 or 1, elementary graphs, and 1-tough graphs.     

Reachability sets of hybrid systems in the presence of successive switchings

The concept of reachability domains of hybrid systems is described together with the use of ellipsoidal methods for calculation of such domains in the case when there are successive switchings on several given hyperplanes or bands. An algorithm for calculation of the reachability sets for a hybrid system that uses ellipsoidal approximations is given for the cases in which the switching sets are planes or bands. The parametrization of nonconvex reachability domains is obtained as a union of intersections of the corresponding ellipsoidal estimates.     

Topological complexity of Julia sets

The topological structures of the Julia sets of rational and entire functions have been investigated and the complexity of the Julia sets of rational functions has been described. For entire functions, it is proved that the dynamics on the Fatou sets will influence the topological complexity of Julia sets.     

Optimum signal and image recovery by the method of alternating projections in fractional Fourier domains

This paper presents a signal and image recovery scheme by the method of alternating projections onto convex sets in optimum fractional Fourier domains. It is shown that the fractional Fourier domain order with minimum bandwidth is the optimum fractional Fourier domain for the method employing alternating projections in signal recovery problems. Following the estimation of optimum fractional Fourier transform orders, incomplete signal is projected onto different convex sets consecutively to restore the missing part. Using a priori information in optimum fractional Fourier domains, superior results are obtained compared to the conventional Fourier domain restoration. The algorithm is tested on 1-D linear frequency modulated signals, real biological data and 2-D signals presenting chirp-type characteristics. Better results are obtained in the matched fractional Fourier domain, compared to not only the conventional Fourier domain restoration, but also other fractional Fourier domains.     

On the complexity of finding paths in a two‐dimensional domain I: Shortest paths

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: (A) domains with polynomialtime computable boundaries, and (B) 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 (A) and type (B); and it has a polynomial‐space lower bound for the domains of type (B), and has a #P lower bound for the domains of type (A). (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

相容连续Domain的遗传性

定义相容Domain的子Domain与子空间等概念,得到Scott开集和Scott闭集都是相容Domain的子Domain与子空间的结论,证明了相容连续Domain或相容代数Domain对开子空间和闭子空间都是可遗传的。     

On the index sets of Σ-subsets of the real numbers

We compute the levels of complexity in analytical and arithmetical hierarchies for the sets of the Σ-formulas defining in the hereditarily finite superstructure over the ordered field of the reals the classes of open, closed, clopen, nowhere dense, dense subsets of ? ⁿ , first category subsets in ? ⁿ as well as the sets of pairs of Σ-formulas corresponding to the relations of set equality and inclusion which are defined by them. It is also shown that the complexity of the set of the Σ-formulas defining connected sets is at least Π ₁ ¹ .     

On the order and type of basic and composite sets of polynomials in complete Reinhardt domains

In this paper we will define the order and type of basic and composite sets of polynomials of several complex variables in complete Reinhardt domains. Also, the property of basic and composite sets of polynomials of several complex variables in complete Reinhardt domains is discussed.     

连续Domain的遗传性及其不变性

引入Domain子空间的概念,得到Scott开集和闭集都是Domain的子空间。证明连续Domain或代数Domain对开子空间和闭子空间都是可遗传的。证明连续Domain或代数Domain在保Waybelow序的Scott连续映射下保持不变。     

Scheduling theory problems of type n¦1∥σci(t)

The class of problems n¦1∥σc_i(t) is considered for special sets of penalty functions c_i(t). Using the structural properties of the sets of functions c_i(t), one selects subclasses of problems which possess a polynomial complexity.     

Fixed‐parameter decidability: Extending parameterized complexity analysis

We extend the reach of fixed‐parameter analysis by introducing classes of parameterized sets defined based on decidability instead of complexity. Known results in computability theory can be expressed in the language of fixed‐parameter analysis, making use of the landscape of these new classes. On the one hand this unifies results that would not otherwise show their kinship, while on the other it allows for further exchange of insights between complexity theory and computability theory. In the landscape of our fixed‐parameter decidability classes, we recover part of the classification of real numbers according to their computability. From this, using the structural properties of the landscape, we get a new proof of the existence of P ‐selective bi‐immune sets. Furthermore, we show that parameter values in parameterized sets in our uniformly fixed‐parameter decidability classes interact with both instance complexity and Kolmogorov complexity. By deriving a parameter based upper bound on instance complexity, we demonstrate how parameters convey a sense of randomness. Motivated by the instance complexity conjecture, we show that the upper bound on the instance complexity is infinitely often also an upper bound on the Kolmogorov complexity.     

Sets of arithmetical invariants in transfer Krull monoids

Transfer Krull monoids are a recently introduced class of monoids and include the multiplicative monoids of all commutative Krull domains as well as of wide classes of non-commutative Dedekind domains. We show that transfer Krull monoids are fully elastic (i.e., every rational number between 1 and the elasticity of the monoid can be realized as the elasticity of an element). In commutative Krull monoids which have sufficiently many prime divisors in all classes of their class group, the set of catenary degrees and the set of tame degrees are intervals. Without the assumption on the distribution of prime divisors, arbitrary finite sets can be realized as sets of catenary degrees and as sets of tame degrees.     

Direct sums of bilinear algorithms

We consider the bilinear complexity of certain sets of bilinear forms. We study a class of direct sums of bilinear forms. For this class of problems we show that the bilinear complexity of one direct sum is the sum of the bilinear complexities of the summands and that every minimal bilinear algorithm for computing the direct sums is a direct-sum algorithm. We also exhibit some sets of bilinear forms which belong to this class.     

Minimization of integral functionals depending on lipschitz domains

In this paper is solved a minimization problem for what is essentially an integral functional depending on domains which verify an uniform cone property with a fixed parameter θ by extending the techniques land results of O. Caligaris and P. Oliva ‘1’ for convex sets. A Dirichlet condition and an obstacle are considered.     

On the Complexity of Minimizing Quasicyclic Boolean Functions

We investigate the Boolean functions that combine various properties: the extremal values of complexity characteristics ofminimization, the inapplicability of local methods for reducing the complexity of the exhaustion, and the impossibility to efficiently use sufficient minimality conditions. Some quasicyclic functions are constructed that possess the properties of cyclic and zone functions, the dominance of vertex sets, and the validity of sufficient minimality conditions based on independent families of sets. For such functions, we obtain the exponential lower bounds for the extent and special sets and also a twice exponential lower bound for the number of shortest and minimal complexes of faces with distinct sets of proper vertices.