A sequentially computable function that is not effectively continuous at any point

P. Hertling [Lecture Notes in Computer Science, vol. 2380, Springer, Berlin, 2002, pp. 962–972; Ann. Pure Appl. Logic 132 (2005) 227–246] showed that there exists a sequentially computable function mapping all computable real numbers to computable real numbers that is not effectively continuous. Here, that result is strengthened: a sequentially computable function on the computable real numbers is constructed that is not effectively continuous at any point.     

Algorithmic randomness of continuous functions

We investigate notions of randomness in the space ${{\mathcal C}(2^{\mathbb N})}We investigate notions of randomness in the space of continuous functions on . A probability measure is given and a version of the Martin-L?f test for randomness is defined. Random continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any , there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set. Research partially supported by the National Science Foundation grants DMS 0532644 and 0554841 and 00652732. Thanks also to the American Institute of Mathematics for support during 2006 Effective Randomness Workshop; Remmel partially supported by NSF grant 0400307; Weber partially supported by NSF grant 0652326. Preliminary version published in the Third International Conference on Computability and Complexity in Analysis, Springer Electronic Notes in Computer Science, 2006.     

Complexity and T ‐invariant of Abelian and Milnor groups,and complexity of 3‐manifolds

We investigate the notion of complexity for finitely presented groups and the related notion of complexity for three‐dimensional manifolds. We give two‐sided estimates on the complexity of all the Milnor groups (the finite groups with free action on S³), as well as for all finite Abelian groups. The ideas developed in the process also allow to construct two‐sided bounds for the values of the so‐called T ‐invariant (introduced by Delzant) for the above groups, and to estimate from below the value of T ‐invariant for an arbitrary finitely presented group. Using the results of this paper and of previous ones, we then describe an infinite collection of Seifert threemanifolds for which we can asymptotically determine the complexity in an exact fashion up to linear functions. We also provide similar estimates for the complexity of several infinite families of Milnor groups. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the computational complexity of the theory of Abelian groups

We develop a series of Ehrenfeucht games and prove the following results:

• 1.(i) The first order theory of the divisible and indecomposable p-group, the first order theory of the group of rational numbers with denominators prime to p and the first order theory of a cyclic group of prime power order can be decided in 2^{2cn log n} Turing time.
• 2.(ii) The first order theory of the direct sum of countably many infinite cyclic groups, the first order theory of finite Abelian groups and the first order theory of all Abelian groups can be decided in 2^2dn Turing space.

     

Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups

A pseudo-natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a word w equals 1 in the group but also gives a derivation of 1 from w when w equals 1. In [13], [14] Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo-natural algorithm is arbitrarily more complicated than an algorithm which simply solves the word problem. In a given group the lowest degree of complexity that can be realised by a pseudo-natural algorithm is essentially the derivational complexity of that group. Thus the result separates the derivational complexity of the word problem of a finitely presented group from its intrinsic complexity. The proof given in [13] involves the construction of a finitely presented group G from a Turing machine T such that the intrinsic complexity of the word problem for G reflects the complexity of the halting problem of T, while the derivational complexity of the word problem for G reflects the runtime complexity of T. The proof of one of the crucial lemmas in [13] is only sketched, and part of the purpose of this paper is to give the full details of this proof. We will also obtain a variant of their proof, using modular machines rather than Turing machines. As for several other results, this simplifies the proofs considerably. MSC: 03D40, 20F10.     

Directional complexity of the hypercubic billiard

We consider a minimal rotation on the torus T^d of direction ω. A natural cellular decomposition of the torus is associated to this map. We consider an infinite orbit for this map. We compute the complexity of the associated word. Under some hypothesis on the direction, we obtain an exact formula which shows that the order of magnitude is n^d. This result is related to the billiard map inside a hypercube of R^d+1.     

The complexity of computing a robust flow

The Maximum Robust Flow problem asks for a flow on the paths of a network maximizing the guaranteed amount of flow surviving the removal of any $k$ arcs. We point out a flaw in a previous publication that claimed $NP$-hardness for this problem when $k=2$. For the case that $k$ is part of the input, we present a new hardness proof. We also discuss the complexity of the integral version of the problem.     

Finite computable dimension and degrees of categoricity

We first give an example of a rigid structure of computable dimension 2 such that the unique isomorphism between two non-computably isomorphic computable copies has Turing degree strictly below ${\mathbf{0}}^{″}$, and not above ${\mathbf{0}}^{\prime }$. This gives a first example of a computable structure with a degree of categoricity that does not belong to an interval of the form $[{\mathbf{0}}^{(\alpha )},{\mathbf{0}}^{(\alpha +1)}]$ for any computable ordinal α. We then extend the technique to produce a rigid structure of computable dimension 3 such that if ${\mathbf{d}}_0$, ${\mathbf{d}}_1$, and ${\mathbf{d}}_2$ are the degrees of isomorphisms between distinct representatives of the three computable equivalence classes, then each ${\mathbf{d}}_i<{\mathbf{d}}_0\oplus {\mathbf{d}}_1\oplus {\mathbf{d}}_2$. The resulting structure is an example of a structure that has a degree of categoricity, but not strongly.     

The complexity of social groups and social systems described by graph structures

This paper presents methodology which permits the complete ranking of nondirected graphs (NDG's) on an attribute labelled ‘complexity.’ The technique applies to both small and large systems as might arise in studies of group or organization behavior. The methodology extends to cover the complexity of directed graphs (DG's) and permits the detailed specification of individual and group behavior.For the NDG an abstract automaton representing the participants' interaction or communications function is sited at each node. Each automaton is constructed so its internal complexity is sufficient to realize the minimal social action (e.g. transmission of a rumor and the path followed by the rumor) within the framework of the NDG. It is shown that the complexity of each node automaton depends upon the order of the graph, the degree of the node and the longest path parameter of the graph. The combined complexity of node automata constitutes the complexity of the NDG. The complexity of a DG is specified as a composition of complexities computed for the associated NDG and logical devices which produce the observed behavior. Illustrative examples pertaining to the committee-subcommittee problem and to organizational structures are presented.     

Abelian C-minimal groups

Macpherson and Steinhorn (Macpherson and Steinhorn, Ann. Pure Appl. Logic 79 (1996) 165–209) introduce some variants of the notion of o-minimality. One of the most interesting is C-minimality, which provides a natural setting to study algebraically closed-valued fields and some valued groups. In this paper we go further in the study of the structure of C-minimal valued groups, giving a partial characterization in the abelian case. We obtain the following principle: for abelian valued groups G for which the valuation satisfies some kind of compatibility with the multiplication by any prime number p, being C-minimal is equivalent to the o-minimality of the expansion of the chain of valuations by the maps induced by the multiplication by each prime number in G, and by some unary predicates controlling the cardinality of the residual structures. This result is quite nice, because the class considered contains all the natural examples of abelian C-minimal valued groups of (Macpherson and Steinhorn, Ann. Pure Appl. Logic 79 (1996) 165–209), and allows us to find many more examples.     

Abelian groups as autocommutator groups

In this article, we establish that every finite abelian group is isomorphic to the autocommutator subgroup of some finite abelian group. Received: 21 September 2007     

Biembeddings of Abelian groups

We prove that, with the single exception of the 2‐group C, the Cayley table of each Abelian group appears in a face 2‐colorable triangular embedding of a complete regular tripartite graph in an orientable surface. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 71–83, 2010     

On the computability-theoretic complexity of trivial, strongly minimal models

We show the existence of a trivial, strongly minimal (and thus uncountably categorical) theory for which the prime model is computable and each of the other countable models computes . This result shows that the result of Goncharov/Harizanov/Laskowski/Lempp/McCoy (2003) is best possible for trivial strongly minimal theories in terms of computable model theory. We conclude with some remarks about axiomatizability.

     

Computing the complexity for Schelling segregation models

The Schelling segregation models are “agent based” population models, where individual members of the population (agents) interact directly with other agents and move in space and time. In this note we study one-dimensional Schelling population models as finite dynamical systems. We define a natural notion of entropy which measures the complexity of the family of these dynamical systems. The entropy counts the asymptotic growth rate of the number of limit states. We find formulas and deduce precise asymptotics for the number of limit states, which enable us to explicitly compute the entropy.