Grammatical Complexity of Feigenbaum Attractor

The Feigenbaum attractor is an important case in the dynamical systems of one-dimensional maps . In this paper we analyze the grammatical complexity of theFeigenbaum attractor, using both theories of symbolic dynamics and of formal lan-guages . In the Chomsky's hierarchy, formal languages are classified into fourlevels: regular languages, context-free languages, context-sensitive languages and re-cursively enumerable languages. It was shown in [6] that for one-dimensional cellularautomata, the sets of configurations generated after a finite number of time steps of     

The Coding Complexity of Lévy Processes

We introduce a new coding scheme for general real-valued Lévy processes and control its performance with respect to L _p [0,1]-norm distortion under different complexity constraints. We also establish lower bounds that prove the optimality of our coding scheme in many cases.      

What Is the Complexity of Surface Integration?

We study the worst case complexity of computing ε-approximations of surface integrals. This problem has two sources of partial information: the integrand f and the function g defining the surface. The problem is nonlinear in its dependence on g. Here, f is an r times continuously differentiable scalar function of l variables, and g is an s times continuously differentiable injective function of d variables with l components. We must have d⩽l and s⩾1 for surface integration to be well-defined. Surface integration is related to the classical integration problem for functions of d variables that are min{r, s−1} times continuously differentiable. This might suggest that the complexity of surface integration should be Θ((1/ε)^{d/min{r, s−1}}). Indeed, this holds when d<l and s=1, in which case the surface integration problem has infinite complexity. However, if d⩽l and s⩾2, we prove that the complexity of surface integration is O((1/ε)^d/min{r, s}). Furthermore, this bound is sharp whenever d<l.     

What Is the Complexity of Stieltjes Integration?

We study the complexity of approximating the Stieltjes integral ∫¹₀ f(x) dg(x) for functions f having r continuous derivatives and functions g whose sth derivative has bounded variation. Let r(n) denote the nth minimal error attainable by approximations using at most n evaluations of f and g, and let comp(ε) denote the ε-complexity (the minimal cost of computing an ε-approximation). We show that r(n)≍n^{−min{r, s+1}} and that comp(ε)≍ε^{−1/min{r, s+1}}. We also present an algorithm that computes an ε-approximation at nearly minimal cost.     

Complexity Estimates for the Schmüdgen Positivstellensatz

LetKbe a closed basic set inRⁿgiven by the polynomial inequalities φ₁≥ 0, . . . , φ_m≥ 0 and let Σ be the semiring generated by the φ_kand the squares inR[x₁, . . . ,x_n]. Schmüdgen has shown that ifKis compact then any polynomial function strictly positive onKbelongs to Σ. Easy consequences are (1)f≥ 0 onKif and only iff∈R⁺+ Σ (Positivstellensatz) and (2) iff≥ 0 onKbutf∈ Σ then asdtends to 0⁺, in any representation off + das an element of Σ in terms of the φ_k, the squares and semiring operations, the integerN(d) which is the minimum over all representations of the maximum degree of the summands must become arbitrarily large. A one-dimensional example is analyzed to obtain asymptotic lower and upper bounds of the formcd^−1/2≤N(d) ≤Cd^−1/2log (1/d).     

An Algorithm for l∞ Regression with Quadratic Complexity

Using a few very basic observations, we proposed recently a direct and finite algorithm for the computation of the l regression line on a discrete set under the assumption that In this paper, we extend the algorithm to the case with at least one, possibly multiple y-values for each distinct x_i. Our algorithm finds all the regression lines in O(n ²) operations in the worst-case scenario and improves the existing best-known computational complexity result for this problem. Numerical results on random problems are included.     

Complexity Estimates for Representations of Schmüdgen Type

Let Φ={φ₁, …, φ_j} and let K be a closed basic set in Rⁿ given by the polynomial inequalities φ₁⩾0, …, φ_j⩾0. Let Σ{Φ} be the semiring generated by the φ_k and the squares in R[x₁, …, x_n]. For example, if Φ={φ₁} then Σ{Φ}=σ₁+σ₂φ₁, where σ₁, σ₂ are sums of squares of polynomials. Schmüdgen has shown that if K is compact then any polynomial strictly positive on K belongs to Σ{Φ}. This paper develops a result of Schmüdgen type for functions in one dimension merely nonnegative on K. For this, it is necessary to add additional hypotheses, such as the proximity of complex zeros, to compensate for the loss of strict positivity necessary for Schmüdgen's result.     

What Is the Complexity of Solution-Restricted Operator Equations?

We study the worst case complexity of operator equations Lu = f where L: G → X is a bounded linear injection of normed linear spaces. Past work on the complexity of such problems has generally required the class F of problem elements f to be the unit ball of X. However, there are many problems for which this choice of F yields unsatisfactory results. Mixed elliptic—hyperbolic problems are one example. the difficulty being that our technical tools are nor strong enough to give good complexity bounds. Ill-posed problems are another example. because we know that the complexity of computing finite-error approximations is infinite if F is a ball in X. In this paper, we pursue another idea. Rather than directly restrict the class F of problem elements f, we will consider problems that are solution-restricted: i.e., we restrict the class U of solution elements u. In particular, we assume that U is the unit hall of a normed linear space W that is densely, continuously embedded in G. The main idea is that our problem can now be reduced to the standard approximation problem of approximating the embedding of W into G.This allows us to characterize optimal information and algorithms for our problem..We use this idea to study three problems: the Tricomi problem (a mixed hyperbolic— elliptic problem arising in the study of transonic flow), the inverse finite Laplace transform (an ill-posed problem arising. e.g.. in geomathematics), and the backwards heat equation. We determine the problem complexity and derive nearly optimal algorithms for each of these problems.     

Complexity of fuzzy answer set programming under Łukasiewicz semantics

Fuzzy answer set programming (FASP) is a generalization of answer set programming (ASP) in which propositions are allowed to be graded. Little is known about the computational complexity of FASP and almost no techniques are available to compute the answer sets of a FASP program. In this paper, we analyze the computational complexity of FASP under Łukasiewicz semantics. In particular we show that the complexity of the main reasoning tasks is located at the first level of the polynomial hierarchy, even for disjunctive FASP programs for which reasoning is classically located at the second level. Moreover, we show a reduction from reasoning with such FASP programs to bilevel linear programming, thus opening the door to practical applications. For definite FASP programs we can show P-membership. Surprisingly, when allowing disjunctions to occur in the body of rules – a syntactic generalization which does not affect the expressivity of ASP in the classical case – the picture changes drastically. In particular, reasoning tasks are then located at the second level of the polynomial hierarchy, while for simple FASP programs, we can only show that the unique answer set can be found in pseudo-polynomial time. Moreover, the connection to an existing open problem about integer equations suggests that the problem of fully characterizing the complexity of FASP in this more general setting is not likely to have an easy solution.     

On the Complexity of the Julia Sets of Rational Functions

ＯｎｔｈｅＣｏｍｐｌｅｘｉｔｙｏｆｔｈｅＪｕｌｉａＳｅｔｓｏｆＲａｔｉｏｎａｌＦｕｎｃｔｉｏｎｓＱｉａｏＪｉａｎｙｏｎｇ（乔建永）（ＩｎｓｔｉｔｕｔｅｏｆＭａｔｈｅｍａｔｉｃｓ，ＡｃａｄｅｍｉａＳｉｎｉｃａ，Ｂｅｉｊｉｎｇ，１０００８０）Ｃｏｍｍｕｎ...     

Nonlinear Lebesgue and Itô Integration Problems of High Complexity

We analyze the complexity of nonlinear Lebesgue integration problems in the average case setting for continuous functions with the Wiener measure and the complexity of approximating the Itô stochastic integral. G. W. Wasilkowski and H. Woźniakowski (2001, Math. Comp., 685–698) studied these problems, observed that their complexities are closely related, and showed that for certain classes of smooth functions with boundedness conditions on derivatives the complexity is proportional to ε⁻¹. Here ε>0 is the desired precision with which the integral is to be approximated. They showed also that for certain natural function classes with weaker smoothness conditions the complexity is at most of order ε⁻² and conjectured that this bound is sharp. We show that this conjecture is true.     

On Fast Polynomial Algorithms and Lower Bounds of the Linear Complexity

ＯｎＦａｓｔＰｏｌｙｎｏｍｉａｌＡｌｇｏｒｉｔｈｍｓａｎｄＬｏｗｅｒＢｏｕｎｄｓｏｆｔｈｅＬｉｎｅａｒＣｏｍｐｌｅｘｉｔｙＬｉＬｅｉ（李磊）（Ｘｉ＇ａｎＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｘｉ＇ａｎ，Ｃｈｉｎａ，＆ＡｏｍｏｒｉＵｎｉｖｅｒｓｉｔｙ，...     

Computing Matveev’s Complexity via Crystallization Theory: The Orientable Case

By means of a slight modification of the notion of GM-complexity introduced in [Casali, M.R., Topol. Its Appl., 144: 201–209, 2004], the present paper performs a graph-theoretical approach to the computation of (Matveev’s) complexity for closed orientable 3-manifolds. In particular, the existing crystallization catalogue available in [Lins, S., Knots and Everything 5, World Scientific, Singapore, 1995] is used to obtain upper bounds for the complexity of closed orientable 3-manifolds triangulated by at most 28 tetrahedra. The experimental results actually coincide with the exact values of complexity, for all but three elements. Moreover, in the case of at most 26 tetrahedra, the exact value of the complexity is shown to be always directly computable via crystallization theory.     

Complexity analysis of spatial–temporal precipitation system by PCA and SDLE

In this paper, an ensemble technique combining the principal component analysis (PCA) with scale-dependent Lyapunov exponent (SDLE) is used to characterize complexity of precipitation dynamical system. The spatial–temporal precipitation data is decomposed by employing PCA method and then the SDLE for the first few principal components (PCs) time series are computed. The first few PCs time series are found to exhibit the different scaling laws on different time scales. The study illustrate that the spatial–temporal precipitation data is chaotic and the precipitation system is truly multiscaled and complex.     

The Effect of Corners on the Complexity of Approximate Range Searching

Given an n-element point set in ℝ ^d , the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range η can be determined quickly. In ε-approximate range searching we assume that η is bounded, and the sum is required to include all the points that lie within η and may additionally include any of the points lying within distance ε⋅diam(η) of η’s boundary. In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space. A semigroup (S,+) is idempotent if x+x=x for all x∈S, and it is integral if for all k≥2, the k-fold sum x+⋅⋅⋅+x is not equal to x. Recent research has shown that the computational complexity of approximate spherical range searching is significantly lower for idempotent semigroups than it is for integral semigroups in terms of the dependencies on ε. In this paper we consider whether these results can be generalized to other sorts of ranges. We show that, as with integrality, allowing sharp corners on ranges has an adverse effect on the complexity of the problem. In particular, we establish lower bounds on the worst-case complexity of approximate range searching in the semigroup arithmetic model for ranges consisting of d-dimensional unit hypercubes under rigid motions. We show that for arbitrary (including idempotent) semigroups and linear space, the query time is at least . In the case of integral semigroups we prove a tighter lower bound of Ω(1/ε ^d−2). These lower bounds nearly match existing upper bounds for arbitrary semigroups. In contrast, we show that the improvements offered by idempotence do apply to smooth convex ranges. We say that a range is smooth if at every boundary point there is an incident Euclidean sphere that lies entirely within the range whose radius is proportional to the range’s diameter. We show that for smooth ranges and idempotent semigroups, ε-approximate range queries can be answered in O(log n+(1/ε)^(d−1)/2log (1/ε)) time using O(n/ε) space. We show that this is nearly tight by presenting a lower bound of Ω(log n+(1/ε)^(d−1)/2). This bound is in the decision-tree model and holds irrespective of space. A preliminary version of this paper appeared in the Proc. 22nd Annu. ACM Sympos. Comput. Geom., pp. 11–20, 2006. The research of S. Arya was supported by the Research Grants Council, Hong Kong, China under project number HKUST6184/04E. The research of D.M. Mount was partially supported by the National Science Foundation under grant CCR-0635099 and the Office of Naval Research under grant N00014-08-1-1015.