On the complexity of labeled oriented trees

We define a notion of complexity for labeled oriented trees (LOTs) related to the bridge number in knot theory and prove that LOTs of complexity 2 are aspherical. We also present a class of LOTs of higher complexity which is aspherical, give an upper bound for the complexity of labeled oriented intervals and study the complexity of torus knots.     

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.     

Analytical properties of resource-bounded real functionals

Computable analysis is an extension of classical discrete computability by enhancing the normal Turing machine model. It investigates mathematical analysis from the computability perspective. Though it is well developed on the computability level, it is still under developed on the complexity perspective, that is, when bounding the available computational resources. Recently Kawamura and Cook developed a framework to define the computational complexity of operators arising in analysis. Our goal is to understand the effects of complexity restrictions on the analytical properties of the operator. We focus on the case of norms over C[0, 1] and introduce the notion of dependence of a norm on a point and relate it to the query complexity of the norm. We show that the dependence of almost every point is of the order of the query complexity of the norm. A norm with small complexity depends on a few points but, as compensation, highly depends on them. We briefly show how to obtain similar results for non-deterministic time complexity. We characterize the functionals that are computable using one oracle call only and discuss the uniformity of that characterization.     

Playing off-line games with bounded rationality

We study a two-person zero-sum game where players simultaneously choose sequences of actions, and the overall payoff is the average of a one-shot payoff over the joint sequence. We consider the maxmin value of the game played in pure strategies by boundedly rational players and model bounded rationality by introducing complexity limitations. First we define the complexity of a sequence by its smallest period (a nonperiodic sequence being of infinite complexity) and study the maxmin of the game where player 1 is restricted to strategies with complexity at most n and player 2 is restricted to strategies with complexity at most m. We study the asymptotics of this value and a complete characterization in the matching pennies case. We extend the analysis of matching pennies to strategies with bounded recall.     

Qubit complexity of continuous problems

The number of qubits used by a quantum algorithm will be a crucial computational resource for the foreseeable future. We show how to obtain the classical query complexity for continuous problems. We then establish a simple formula for a lower bound on the qubit complexity in terms of the classical query complexity.     

Little perfection and complexity

We consider the infinitely-repeated prisoners' dilemma with lexicographic complexity costs, where transitional complexity between states is included as one aspect of overall strategic complexity. We prove that a full folk theorem obtains in presence of any level of perfection of the equilibrium strategy, if the players consider off-equilibrium path payoff prior to minimizing complexity.This work was partially done while the author was visiting at Department of Managerial Economics and Decision Sciences, Kellogg Graduate School of Management, Northwestern University, Evanston, Illinois 60208, USA.     

There Exists a Problem Whose Computational Complexity Is Any Given Function of the Information Complexity

We present an information-based complexity problem for which the computational complexity can be any given increasing function of the information complexity, and the information complexity can be any non-decreasing function of ϵ⁻¹, where ϵ is the error parameter.     

Some characteristics of complex behavior of orbits in dynamical systems

We present a brief review of mathematical notions of complexity based on instability of orbits. We show that the complexity as a function of time may grow exponentially in chaotic situations or polynomially for systems with zero topological entropy. At the end we discuss the class of nonchaotic systems for which all orbits are stable but nevertheless behavior of orbits is complex. We introduce a new notion of complexity for such a kind of systems.     

On the permutations generated by Sturmian words

Infinite permutations of use in this article were introduced in [1]. Here we distinguish the class of infinite permutations that are generated by the Sturmian words and inherit their properties. We find the combinatorial complexity of these permutations, describe their Rauzy graphs, frequencies of subpermutations, and recurrence functions. We also find their arithmetic complexity and Kamae complexity.     

A Theory of Complexity for Continuous Time Systems

We present a model of computation with ordinary differential equations (ODEs) which converge to attractors that are interpreted as the output of a computation. We introduce a measure of complexity for exponentially convergent ODEs, enabling an algorithmic analysis of continuous time flows and their comparison with discrete algorithms. We define polynomial and logarithmic continuous time complexity classes and show that an ODE which solves the maximum network flow problem has polynomial time complexity. We also analyze a simple flow that solves the Maximum problem in logarithmic time. We conjecture that a subclass of the continuous P is equivalent to the classical P.     

Modules with Reducible Complexity,II

We continue studying the class of modules having reducible complexity over a local ring. In particular, a method is provided for computing an upper bound of the complexity of such a module, in terms of vanishing of certain cohomology modules. We then specialize to complete intersections, which are precisely the rings over which all modules have finite complexity.     

Generating Functions for Computing the Myerson Value

The complexity of a computational problem is the order of computational resources which are necessary and sufficient to solve the problem. The algorithm complexity is the cost of a particular algorithm. We say that a problem has polynomial complexity if its computational complexity is a polynomial in the measure of input size. We introduce polynomial time algorithms based in generating functions for computing the Myerson value in weighted voting games restricted by a tree. Moreover, we apply the new generating algorithm for computing the Myerson value in the Council of Ministers of the European Union restricted by a communication structure.     

A general framework for measuring system complexity

In this work, we are motivated by the observation that previous considerations of appropriate complexity measures have not directly addressed the fundamental issue that the complexity of any particular matter or thing has a significant subjective component in which the degree of complexity depends on available frames of reference. Any attempt to remove subjectivity from a suitable measure therefore fails to address a very significant aspect of complexity. Conversely, there has been justifiable apprehension toward purely subjective complexity measures, simply because they are not verifiable if the frame of reference being applied is in itself both complex and subjective. We address this issue by introducing the concept of subjective simplicity—although a justifiable and verifiable value of subjective complexity may be difficult to assign directly, it is possible to identify in a given context what is “simple” and, from that reference, determine subjective complexity as distance from simple. We then propose a generalized complexity measure that is applicable to any domain, and provide some examples of how the framework can be applied to engineered systems. © 2016 Wiley Periodicals, Inc. Complexity 21: 533–546, 2016     

The complexity of the free space for a robot moving amidst fat obstacles

We propose a new definition of fatness of geometric objects and compare it with alternative definitions. We show that, under some realistic assumptions, the complexity of the free space for a robot, with any fixed number of degrees of freedom moving in a d-dimensional Euclidean workspace with fat obstacles, is linear in the number of obstacles. The complexity of motion planning algorithms depends on the complexity of the robot's free space, and theoretically, the complexity of the free space can be very high. Thus, our result opens the way to devising provable efficient motion planning algorithms in certain realistic settings.     

Some Notes on the Linear Complexity of Sidel’nikov-Lempel-Cohn-Eastman Sequences

We continue the study of the linear complexity of binary sequences, independently introduced by Sidel’nikov and Lempel, Cohn, and Eastman. These investigations were originated by Helleseth and Yang and extended by Kyureghyan and Pott. We determine the exact linear complexity of several families of these sequences using well-known results on cyclotomic numbers. Moreover, we prove a general lower bound on the linear complexity profile for all of these sequences.     

Complexity and asymptotic stability in the process of biochemical substance exchange in a coupled ring of cells

We have considered the complexity and asymptotic stability in the process of biochemical substance exchange in a coupled ring of cells. We have used coupled maps to model this process. It includes the coupling parameter, cell affinity and environmental factor as master parameters of the model. We have introduced: (i) the Lempel–Ziv complexity spectrum and (ii) the Lempel–Ziv complexity spectrum highest value to analyze the dynamics of two cell model. The asymptotic stability of this dynamical system using an eigenvalue-based method has been considered. Using these complexity measures we have noticed an “island” of low complexity in the space of the master parameters for the weak coupling. We have explored how stability of the equilibrium of the biochemical substance exchange in a multi-cell system (N = 100) is influenced by the changes in the master parameters of the model for the weak and strong coupling. We have found that in highly chaotic conditions there exists space of master parameters for which the process of biochemical substance exchange in a coupled ring of cells is stable.     

There Exists a Linear Problem with Infinite Combinatory Complexity

We present a linear problem whose information complexity is finite but whose combinatory complexity is infinite. Thus, this linear problem has infinite complexity due to infinite combinatory complexity and not due to information complexity. This holds in a real number model in which we only allow arithmetic operations, comparisons of real numbers as well as precomputation of finitely many arbitrary elements. The result is not true if we can also evaluate logarithms, exponentials, and ceilings.     

On the linear complexity profile of some new explicit inversive pseudorandom numbers

Linear complexity and linear complexity profile are interesting characteristics of a sequence for applications in cryptography and Monte-Carlo methods. We introduce some new explicit inversive pseudorandom number generators and prove lower bounds on their linear complexity profile which are close to the best possible.     

Developing and refining a framework for mathematical and linguistic complexity in tasks related to rates of change

We present and develop a preliminary framework for describing the relationship between the mathematical and linguistic complexity of instructional tasks used in secondary mathematics. The initial framework was developed through a review of relevant literature. It was refined by examining how 4 ninth grade mathematics teachers of linguistically diverse groups of students described the linguistic and mathematical complexity of a set of tasks from their curriculum unit on linear functions. We close by presenting our refined framework for describing the interaction of linguistic complexity and mathematical complexity in curriculum materials, and discuss potential uses of this framework in the design of more accessible classroom learning environments for linguistically diverse students.     

On the robust assignment problem under a fixed number of cost scenarios

We investigate the complexity of the min-max assignment problem under a fixed number of scenarios. We prove that this problem is polynomial-time equivalent to the exact perfect matching problem in bipartite graphs, an infamous combinatorial optimization problem of unknown computational complexity.