Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem

We consider the problem of maintaining a dynamic ordered set of n integers in a universe U under the operations of insertion, deletion and predecessor queries. The computation model used is a unit-cost RAM, with a word length of w bits, and the universe size is |U|=2^w. We present a data structure that uses O(|U|/log|U|+n) space, performs all the operations in O(loglog|U|) time and needs O(loglog|U|/logloglog|U|) structural changes per update operation. The data structure is a simplified version of the van Emde Boas' tree introducing, in its construction and functioning, new concepts, which help to keep the important information for searching along the path of the tree, in a more compact and organized way.     

Computational Complexity in Algebraic Systems

Computability and computational complexity were first considered over the fields of real and complex numbers and generalized to arbitrary algebraic systems. This article approaches the theory of computational complexity over an arbitrary algebraic system by taking computability over the list extension for a computational model of it. We study the resultant polynomial complexity classes and mention some NP-complete problems.     

具有非单调功能反应和脉冲扰动的捕食系统的研究

研究捕食者具有非单调功能反应和周期脉冲扰动的捕食者一食饵系统，利用脉冲微分方程的Floquet理论和比较定理，得到了系统灭绝和持续生存的充分条件．最后，通过数值模拟阐明系统在周期脉冲扰动下的复杂性．     

The emergence of dynamical complexity: An exploration using elementary cellular automata

This work concerns the interaction between two classical problems: the forecasting of the dynamical behaviors of elementary cellular automata (ECA) from its intrinsic mathematical laws and the conditions that determine the emergence of complex dynamics. To approach these problems, and inspired by the theory of reversible logical gates, we decompose the ECA laws in a “spectrum” of dyadic Boolean gates. Emergent properties due to interactions are captured generating another spectrum of logical gates. The combined analysis of both spectra shows the existence of characteristic bias in the distribution of Boolean gates for ECA belonging to different dynamical classes. These results suggest the existence of signatures capable to indicate the propensity to develop complex dynamics. Logical gates “exclusive‐or” and “equivalence” are among these signatures of complexity. An important conclusion is that within ECA space, interactions are not capable to generate signatures of complexity in the case these signatures are absent in the intrinsic law of the automaton. © 2004 Wiley Periodicals, Inc. Complexity 9: 33–42, 2004     

Problems, Models and Complexity. Part II: Application to the DLSP

In Part I of this study, we suggest to identify an operations research (OR) problem with the equivalence class of models describing the problem and enhance the standard computer-science theory of computational complexity to be applicable to this situation of an often model-based OR context. The Discrete Lot-sizing and Scheduling Problem (DLSP) is analysed here in detail to demonstrate the difficulties which can arise if these aspects are neglected and to illustrate the new theoretical concept. In addition, a new minimal model is introduced for the DLSP which makes this problem eventually amenable to a rigorous analysis of its computational complexity.     

Some properties of the bilevel programming problem

The purpose of this paper is to elaborate on the difficulties accompanying the development of efficient algorithms for solving the bilevel programming problem (BLPP). We begin with a pair of examples showing that, even under the best of circumstances, solutions may not exist. This is followed by a proof that the BLPP is NP-hard.This work was partially supported by a grant from the Advanced Research Program of the Texas Higher Education Coordinating Board.     

On the complexity of suboptimal decoding for list and decision feedback schemes

We consider bounded distance list decoding, such that the decoder calculates the list of all codewords within a sphere around the received vector. We analyze the performance and the complexity of this suboptimum list decoding scheme for the binary symmetric channel. The reliability function of the list decoding scheme is equivalent to the sphere-packing bound, where the decoding complexity is asymptotically bounded by 2^nR(1-R). Furthermore, we investigate a decision feedback strategy that is based on bounded distance list decoding. Here, any output with zero or many codewords will call for a repeated transmission. In this case the decoding complexity will be of the order 2^nR(1-C), where C denotes the channel capacity. The reliability function is close to Forney's feedback exponent.