Out-of-band quasiseparable matrices

We study structured matrices which consist of a band part and quasiseparable parts below and upper the band. We extend algorithms known for quasiseparable matrices, i.e. for the case when the band consists of the main diagonal only, to a wider class of matrices. The matrices which we consider may be treated as an usual quasiseparable matrices with larger orders of generators. Hence one can apply the methods developed for usual quasiseparable matrices and obtain various linear complexity O(N) algorithms. However in this case the coefficients in N in the complexity estimates turns out to be quite large. In this paper we use the structure more accurately by division of the matrix into three parts in which the middle part is the band instead of diagonal as it is used for usual quasiseparable matrices. This approach allows to use better the structure of the matrix in order to improve the coefficients in N in the complexity estimates for the algorithms. This method works for algorithms which keep invariant the structure.     

Scheduling unit-length jobs with precedence constraints of small height

We consider the problem of scheduling unit-length jobs on identical machines subject to precedence constraints. We show that natural scheduling rules fail when the precedence constraints form a collection of stars or a collection of complete bipartite graphs. We prove that the problem is in fact NP-hard on collections of stars when the input is given in a compact encoding, whereas it can be solved in polynomial time with standard adjacency list encoding. On a subclass of collections of stars and on collections of complete bipartite graphs we show that the problem can be solved in polynomial time even when the input is given in compact encoding, in both cases via non-trivial algorithms.     

Parallel dedicated machines scheduling with chain precedence constraints

A set of n nonpreemptive tasks are to be scheduled on m parallel dedicated machines with a regular criterion. Chain precedence constraints among the tasks, deterministic processing times and processing machine of each task are given.     

Improving understanding,learning, and performances of novices in dynamic managerial simulation games

Simulations are increasingly used in training and education because of their success and their advantages as a learning method. However, it has also been observed that the dynamic complexity of simulations creates learning difficulties, and that performance tends to plateau quickly at a level well below benchmark performance. To overcome this difficulty, a gradual‐increase‐in‐complexity approach is proposed, which suggests developing simpler versions of a simulation game that can be used as part of the training. Accordingly, the authors developed a series of inventory‐management simulations and conducted an experiment. The results indicate an improvement in the success of the inventory‐management simulation as a training tool. © 2009 Wiley Periodicals, Inc. Complexity, 2010     

Maximal pattern complexity of higher dimensional words

This paper studies the pattern complexity of n-dimensional words. We show that an n-recurrent but not n-periodic word has pattern complexity at least 2k, which generalizes the result of [T. Kamae, H. Rao, Y.-M. Xue, Maximal pattern complexity of two dimension words, Theoret. Comput. Sci. 359 (1-3) (2006) 15-27] on two-dimensional words. Analytic directions of a word are defined and its topological properties play a crucial role in the proof.Accordingly n-dimensional pattern Sturmian words are defined. Irrational rotation words are proved to be pattern Sturmian. A new class of higher dimensional words, the simple Toeplitz words, are introduced. We show that they are also pattern Sturmian words.     

Are binary codings universal?

It is common sense to notice that one needs fewer digits to code numbers in ternary than in binary; new names are about log₃2 times shorter. Is this trade-off a consequence of the special coding scheme? The answer is negative. More generally, we argue that the answer to the question, stated in the title and formulated to the first author by C. Rackhoff, is in fact negative. The conclusion will be achieved by studying the role of the size of the alphabet in constructing instantaneous codes for all natural numbers, and defining random strings and sequences. We show that there is no optimal instantaneous code for all positive integers, and the binary is the worst possible. Codes over a fixed alphabet can be indefinitely improved themselves, but only “slightly”; in contrast, changing the size of the alphabet determines a significant, not linear, improvement. The key relation describing the above phenomenon can be expressed in terms of Chaitin complexity: changing the size of the coding alphabet from q to Q, 2 ≤ q < Q, results in an improvement of the complexity by a factor og log q. As a consequence, a string avoiding consistently a fixed letter is not random. In binary, this corresponds to a trivial situation. In the nonbinary case the distinction is relevant: more than 3.2ⁿ ternary strings of length n are not random (many of these strings are binary random). This phenomenon is even sharper for infinite sequences.     

The computational complexity of generating random fractals

We examine a number of models that generate random fractals. The models are studied using the tools of computational complexity theory from the perspective of parallel computation. Diffusion-limited aggregation and several widely used algorithms for equilibrating the Ising model are shown to be highly sequential; it is unlikely they can be simulated efficiently in parallel. This is in contrast to Mandelbrot percolation, which can be simulated in constant parallel time. Our research helps shed light on the intrinsic complexity of these models relative to each other and to different growth processes that have been recently studied using complexity theory. In addition, the results may serve as a guide to simulation physics.     

利用量子纠缠态确定性地降低通信复杂度

文章提出一种确定性地降低两体系系统中的通信复杂度的方案，它利用了一组处于任意纠缠纯态的粒子对。在这个方案中，对于一个任意的两变量布尔函数，一个被通信双方事先分享纠缠态可以使通信复杂度降低。与只通过经典通信或双方仅仅通过交换经典信息相比较而言，利用本方案其通信复杂度降低了一个比特。     

Is the Universe Really That Simple?

The intriguing recent suggestion of Tegmark that the universe—contrary to all our experiences and expectations—contains only a small amount of information due to an extremely high degree of internal symmetry is critically examined. It is shown that there are several physical processes, notably Hawking evaporation of black holes and non-zero decoherence time effects described by Plaga, as well as thought experiments of Deutsch and Tegmark himself, which can be construed as arguments against the low-information universe hypothesis. Some ramifications for both quantum mechanics and cosmology are briefly discussed.     

On the Multiplicative Complexity of the Inversion and Division of Hamiltonian Quaternions

The multiplicative complexity of a finite set of rational functions is the number of essential multiplications and divisions that are necessary and sufficient to compute these rational functions. We prove that the multiplicative complexity of inversion in the division algebra \H of Hamiltonian quaternions over the reals, that is, the multiplicative complexity of the coordinates of the inverse of a generic element from \H , is exactly eight. Furthermore, we show that the multiplicative complexity of the left and right division of Hamiltonian quaternions is at least eleven. July 17, 2001. Final version received: October 8, 2001.