Topological Complexity of Zero-Finding

The topological complexity of zero-finding is studied using a BSS machine over the reals with an information node. The topological complexity depends on the class of functions, the class of arithmetic operations, and on the error criterion. For the root error criterion the following results are established. If only Hölder operations are permitted as arithmetic operations then the topological complexity is roughly −log₂ε and bisection is optimal. This holds even for the small class of linear functions. On the other hand, for the class of all increasing functions, if we allow the sign function or division, together with log and exp, then the topological complexity drops to zero. For the residual error criterion, results can be totally different than for the root error criterion. For example, the topological complexity can be zero for the residual error criterion, and roughly −log₂ε for the root error criterion.     

Combinatorial Complexity of Convex Sequences

We show that the equation \[ s_{i_1}+s_{i_2}+\cdots+s_{i_d}=s_{i_{d+1}}+\cdots+s_{i_{2d}} \] has $O(N^{2d-2+2^{-d+1}})$ solutions for any strictly convex sequence $\{s_i\}_{i=1}^N$ without any additional arithmetic assumptions. The proof is based on weighted incidence theory and an inductive procedure which allows us to deal with higher-dimensional interactions effectively. The terminology "combinatorial complexity" is borrowed from [CES+] where much of our higher-dimensional incidence theoretic motivation comes from.     

Topological Complexity of Motion Planning

   Abstract. In this paper we study a notion of topological complexity TC (X) for the motion planning problem. TC (X) is a number which measures discontinuity of the process of motion planning in the configuration space X . More precisely, TC (X) is the minimal number k such that there are k different "motion planning rules," each defined on an open subset of X× X , so that each rule is continuous in the source and target configurations. We use methods of algebraic topology (the Lusternik—Schnirelman theory) to study the topological complexity TC (X) . We give an upper bound for TC (X) (in terms of the dimension of the configuration space X ) and also a lower bound (in terms of the structure of the cohomology algebra of X ). We explicitly compute the topological complexity of motion planning for a number of configuration spaces: spheres, two-dimensional surfaces, products of spheres. In particular, we completely calculate the topological complexity of the problem of motion planning for a robot arm in the absence of obstacles.     

Topological Complexity of Motion Planning

Abstract. In this paper we study a notion of topological complexity TC (X) for the motion planning problem. TC (X) is a number which measures discontinuity of the process of motion planning in the configuration space X . More precisely, TC (X) is the minimal number k such that there are k different "motion planning rules," each defined on an open subset of X× X , so that each rule is continuous in the source and target configurations. We use methods of algebraic topology (the Lusternik—Schnirelman theory) to study the topological complexity TC (X) . We give an upper bound for TC (X) (in terms of the dimension of the configuration space X ) and also a lower bound (in terms of the structure of the cohomology algebra of X ). We explicitly compute the topological complexity of motion planning for a number of configuration spaces: spheres, two-dimensional surfaces, products of spheres. In particular, we completely calculate the topological complexity of the problem of motion planning for a robot arm in the absence of obstacles.     

Topological Complexity with Continuous Operations

The topological complexity of algorithms is studied in a general context in the first part and for zero-finding in the second part. In the first part thelevel of discontinuityof a functionfis introduced and it is proved that it is a lower bound for the total number of comparisons plus 1 in any algorithm computingfthat uses only continuous operations and comparisons. This lower bound is proved to be sharp if arbitrary continuous operations are allowed. Then there exists even a balanced optimal computation tree forf. In the second part we use these results in order to determine the topological complexity of zero-finding for continuous functionsfon the unit interval withf(0) ·f(1) < 0. It is proved that roughly log₂log₂?⁻¹comparisons are optimal during a computation in order to approximate a zero up to ?. This is true regardless of whether one allows arbitrary continuous operations or just function evaluations, the arithmetic operations {+, −, *, /}, and the absolute value. It is true also for the subclass of nondecreasing functions. But for the subclass of increasing functions the topological complexity drops to zero even for the smaller class of operations.     

Descriptive Complexity and Reflective Properties of Combinatorial Configurations

We study the Ramsey theoretic properties of combinatorial configurationswhich are generated by infinite binary strings which are randomin the sense of Kolmogorov-Chaitin.     

Decoupling Combinatorial Complexity: a Two-Step Approach to Distributions of Runs

Methodology and Computing in Applied Probability - Runs statistics have found many applications in various fields and have attracted attentions of many researchers. Traditional methods used to...     

A Com binatorial Approach for Topological Classification of Graphlike M anifolds

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｔｏｐｏｌｏｇｉｃａｌｃｌａｓｓｉｆｉｃａｔｉｏｎａｎｄｅｎｕｍｅｒａｔｉｏｎｐｒｏｂｌｅｍｏｎｇｒａｐｈｌｉｋｅｍａｎｉｆｏｌｄｓｗａｓｒａｉｓｅｄｉｎ［１］．Ｓｅｖｅｒａｌｒｅｓｕｌｔｓｗｉｔｈｒｅｓｐｅｃｔｔｏｓｐｅｃｉａｌｇｒａｐｈｌｉｋｅｍａｎｉｆｏｌｄｓｗｅｒｅｇｉｖｅｎｉｎ［１～８］．Ｗｅｓｈａｌｌｓｔｕｄｙｔｈｉｓｐｒｏｂｌｅｍｉｎａｖｉｅｗｐｏｉｎｔｏｆｐｕｒｅｃｏｍｂｉｎａｔｏｒｉｃｓ．Ｉｎｆａｃｔ，ａｎｅｗｔｙｐｅｏｆｅｎｕｍｅｒａ－ｔ…     

Combinatorial optimization with interaction costs: Complexity and solvable cases

We introduce and study the combinatorial optimization problem with interaction costs (COPIC). COPIC is the problem of finding two combinatorial structures, one from each of two given families, such that the sum of their independent linear costs and the interaction costs between elements of the two selected structures is minimized. COPIC generalizes the quadratic assignment problem and many other well studied combinatorial optimization problems, and hence covers many real world applications. We show how various topics from different areas in the literature can be formulated as special cases of COPIC. The main contributions of this paper are results on the computational complexity and approximability of COPIC for different families of combinatorial structures (e.g. spanning trees, paths, matroids), and special structures of the interaction costs. More specifically, we analyze the complexity if the interaction cost matrix is parameterized by its rank and if it is a diagonal matrix. Also, we determine the structure of the intersection cost matrix, such that COPIC is equivalent to independently solving linear optimization problems for the two given families of combinatorial structures.     

Topological Complexity of the Relative Closure of a Semi-Pfaffian Couple

Gabrielov introduced the notion of relative closure of a Pfaffian couple as an alternative construction of the o-minimal structure generated by Khovanskii’s Pfaffian functions. In this paper, we use the notion of format (or complexity) of a Pfaffian couple to derive explicit upper bounds for the homology of its relative closure. We consider both the singular and the Borel–Moore homology theories.     

Bochner's Method for Cell Complexes and Combinatorial Ricci Curvature

Abstract. In this paper we present a new notion of curvature for cell complexes. For each p , we define a p th combinatorial curvature function, which assigns a number to each p -cell of the complex. The curvature of a p -cell depends only on the relationships between the cell and its neighbors. In the case that p=1 , the curvature function appears to play the role for cell complexes that Ricci curvature plays for Riemannian manifolds. We begin by deriving a combinatorial analogue of Bochner's theorems, which demonstrate that there are topological restrictions to a space having a cell decomposition with everywhere positive curvature. Much of the rest of this paper is devoted to comparing the properties of the combinatorial Ricci curvature with those of its Riemannian avatar.     

Bochner's Method for Cell Complexes and Combinatorial Ricci Curvature

   Abstract. In this paper we present a new notion of curvature for cell complexes. For each p , we define a p th combinatorial curvature function, which assigns a number to each p -cell of the complex. The curvature of a p -cell depends only on the relationships between the cell and its neighbors. In the case that p=1 , the curvature function appears to play the role for cell complexes that Ricci curvature plays for Riemannian manifolds. We begin by deriving a combinatorial analogue of Bochner's theorems, which demonstrate that there are topological restrictions to a space having a cell decomposition with everywhere positive curvature. Much of the rest of this paper is devoted to comparing the properties of the combinatorial Ricci curvature with those of its Riemannian avatar.     

On the Complexity of Isolating Real Roots and Computing with Certainty the Topological Degree

In this contribution the isolation of real roots and the computation of the topological degree in two dimensions are considered and their complexity is analyzed. In particular, we apply Stenger's degree computational method by splitting properly the boundary of the given region to obtain a sequence of subintervals along the boundary that forms a sufficient refinement. To this end, we properly approximate the function using univariate polynomials. Then we isolate each one of the zeros of these polynomials on the boundary of the given region in various subintervals so that these subintervals form a sufficiently refined boundary.     

Topological Mean Value Relations for Random Cell Complexes

There are investigated stationary random q-dimensional topological cell complexes in ?^d, in particular, random tessellations. General relationships between the mean values of topological characteristics are derived. Then they are specified for the cases d = 2, 3, 4.     

Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces

Let Σ be a collection of n algebraic surface patches in of constant maximum degree b, such that the boundary of each surface consists of a constant number of algebraic arcs, each of degree at most b as well. We show that the combinatorial complexity of the vertical decomposition of a single cell in the arrangement is O(n^{2+ɛ}), for any ɛ > 0, where the constant of proportionality depends on ɛ and on the maximum degree of the surfaces and of their boundaries. As an application, we obtain a near-quadratic motion-planning algorithm for general systems with three degrees of freedom. Received May 30, 1996, and in revised form February 18, 1997.     

一类组合不等式的简证与推广

利用概率方法给出了形如sum from k=1 to n(1/k)>π/4(sum from k=1 to n((-1)k-1Cnk)1/(k～1/2))与sum from k=1 to n(1/k)<2～(1/2)(sum from k=1 to n((-1)k-1Cnk)1/k2)1/2的组合不等式.