On algorithm complexity

This paper contains a review of the authors’ results in the theory of algorithm complexity. The results described concern methods for obtaining lower bounds (containing almost all exponential lower bounds on monotone complexity of monotone functions), synthesis of asymptotically optimal functional networks, minimization of Boolean functions, and the problem of solving Boolean equations.     

On the complexity of growth of the number of distinct fuzzy switching functions

Several attempts have been made to enumerate fuzzy switching (FSF's) and to develop upper and lower bounds for the number of FSF's of n variables in an effort to better understand the properties and the complexity of FSF's. Previous upper bounds are 2⁴ⁿ [9] and 2^{2–3n—2n—1} [7].It has also been shown that the exact numbers of FSF's of n variables for n = 0, 1, 2, 3, and 4 are 2, 6, 8, 84, 43 918 and 160 297 985 276 respectively.This paper will give a brief overview of previous approaches to the problem, study some of the properties of fuzzy switching functions and give improved upper and lower bounds for a general n.     

On the complexity of posets

The purpose of this paper is to discuss several invariants each of which provides a measure of the intuitive notion of complexity for a finite partially ordered set. For a poset X the invariants discussed include cardinality, width, length, breadth, dimension, weak dimension, interval dimension and semiorder dimension denoted respectively X, W(X), L(X), B(X), dim(X). Wdim(X), Idim(X) and Sdim(X). Among these invariants the following inequalities hold. $\text{B(}\text{X}\text{)?Idim(}\text{X}\text{)?Sdim(}\text{X}\text{)?Wdim(}\text{X}\text{)?dim(}\text{X}\text{)?W(}\text{X}\text{)}$. We prove that every poset X with three of more points contains a partly with $\text{Idim}\text{(}\text{X}\text{)}\text{Idim}\text{(}\text{X}\text{) {x,v})}$. If M denotes the set of maximal elements and A an arbitrary anticham of X we show that $\text{Idim}\text{(}\text{X}\text{)?W(}\text{X-M}\text{)}$ and $\text{Idim}\text{(}\text{X}\text{)?2W(}\text{X-A}\text{)}$. We also show that there exist functions f(n,t) and (gt) such that $\text{I(}\text{X}\text{)?n}$ and $\text{Idim}\text{(}\text{X}\text{)?t}$simply $\text{dim}\text{(}\text{X}\text{)?f(n,t and Sdim(}\text{X}\text{)?t}$ implies $\text{dim}\text{(}\text{X}\text{)?g(t)}$.     

On the complexity of calculating factorials

It is shown that n! can be evaluated with time complexity O(log log nM (n log n)), where M(n) is the complexity of multiplying two n-digit numbers together. This is effected, in part, by writing n! in terms of its prime factors. In conjunction with a fast multiplication this yields an O(n(log n log log n)²) complexity algorithm for n!. This might be compared to computing n! by multiplying 1 times 2 times 3, etc., which is ω(n² log n) and also to computing n! by binary splitting which is O(log nM(n log n)).     

On the relation between complexity and uncertainty

In practical problem situations data are usually inherently unreliable. A mathematical representation of uncertainty leads to stochastic optimization problems. In this paper the complexity of stochastic combinatorial optimization problems is discussed. Surprisingly, certain stochastic versions of NP-hard determinstic combinatorial problems appear to be solvable in polynomial time.     

On the complexity of polyhedral separability

It is NP-complete to recognize whether two sets of points in general space can be separated by two hyperplanes. It is NP-complete to recognize whether two sets of points in the plane can be separated withk lines. For every fixedk in any fixed dimension, it takes polynomial time to recognize whether two sets of points can be separated withk hyperplanes.     

On the complexity of diagram testing

In 1987, Neetil and Rödl [4] claimed to have proved that the problem of finding whether a given graphG can be oriented as the diagram of a partial order is NP-complete. A flaw was discovered in their proof by Thostrup [11]. Neetil and Rödl [5] have since corrected the proof, but the new version is rather complex. We give a simpler and more elementary proof, using a completely different approach.     

On the topological complexity of DC-sets

A DC-set is a set defined by means of convex constraints and one additional inverse convex constraint. Given an arbitrary closed subsetM of the Euclideann-space, we show that there exists a DC-set in (n+1)-space being homeomorphic to the given setM. Secondly, for any fixedn2, we construct a compactn-dimensional manifold with boundary, which is a DC-set and which has arbitrarily large Betti-numbersr _k fork n–2.     

On the complexity of computing treelength

We resolve the computational complexity of determining the treelength of a graph, thereby solving an open problem of Dourisboure and Gavoille, who introduced this parameter, and asked to determine the complexity of recognizing graphs of a bounded treelength Dourisboure and Gavoille (2007) [6]. While recognizing graphs with treelength 1 is easily seen as equivalent to recognizing chordal graphs, which can be done in linear time, the computational complexity of recognizing graphs with treelength 2 was unknown until this result. We show that the problem of determining whether a given graph has a treelength at most k is NP-complete for every fixed k≥2, and use this result to show that treelength in weighted graphs is hard to approximate within a factor smaller than . Additionally, we show that treelength can be computed in time O^∗(1.7549ⁿ) by giving an exact exponential time algorithm for the Chordal Sandwich problem and showing how this algorithm can be used to compute the treelength of a graph.     

On the analytic complexity of discriminants

The paper deals with the notion of analytic complexity introduced by V.K. Beloshapka. We give an algorithm which allows one to check whether a bivariate analytic function belongs to the second class of analytic complexity. We also provide estimates for the analytic complexity of classical discriminants and introduce the notion of analytic complexity of a knot.     

On the complexity of task allocation

A detailed study is presented on the combinatorial optimization problem of allocating parallel tasks to a parallel computer. Depending on two application/machine-specific parameters, both a sequential and a parallel optimal allocation phase are shown to exist. A sudden “phase” transition is observed if one of these parameters is varied. Simulated annealing is used to find the optimal allocations, which is justified by the self-similar structure of the task allocation energy landscape. It is shown that the difficulty of finding optimal allocations behaves anomalously near the transition, analogous to critical slowing down of simulated equilibration at second-order phase transitions. © 1997 John Wiley & Sons, Inc.     

On the equational complexity of RRA

We prove that the equational complexity function for the variety of representable relation algebras is bounded below by a log-log function.     

On complexity of subset interconnection designs

Given a setX and subsetsX ₁,...,X _m, we consider the problem of finding a graphG with vertex setX and the minimum number of edges such that fori=1,...,m, the subgraphG _i; induced byX _i is connected. Suppose that for any pointsx ₁,...,x X, there are at mostX _i 's containing the set {x₁,...,x }. In the paper, we show that the problem is polynomial-time solvable for ( 2, 2) and is NP-hard for (3,=1), (=l,6), and (2,3).Support in part by the NSF under grant CCR-9208913 and CCR-8920505.Part work was done while this author was visiting at DIMACS and on leave from Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing.     

On complexity of multistage stochastic programs

In this paper we derive estimates of the sample sizes required to solve a multistage stochastic programming problem with a given accuracy by the (conditional sampling) sample average approximation method. The presented analysis is self-contained and is based on a relatively elementary, one-dimensional, Cramér's Large Deviations Theorem.     

On higher analogs of topological complexity

Farber introduced a notion of topological complexity TC(X) that is related to robotics. Here we introduce a series of numerical invariants TCn(X), n=2,3,… , such that TC₂(X)=TC(X) and TCn(X)?TCn+1(X). For these higher complexities, we define their symmetric versions that can also be regarded as higher analogs of the symmetric topological complexity.