Constructive Dimension and Turing Degrees

This paper examines the constructive Hausdorff and packing dimensions of Turing degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dim _H(S) and constructive packing dimension dim _P(S) is Turing equivalent to a sequence R with dim _H(R)≥(dim _H(S)/dim _P(S))−ε, for arbitrary ε>0. Furthermore, if dim _P(S)>0, then dim _P(R)≥1−ε. The reduction thus serves as a randomness extractor that increases the algorithmic randomness of S, as measured by constructive dimension. A number of applications of this result shed new light on the constructive dimensions of Turing degrees. A lower bound of dim _H(S)/dim _P(S) is shown to hold for the Turing degree of any sequence S. A new proof is given of a previously-known zero-one law for the constructive packing dimension of Turing degrees. It is also shown that, for any regular sequence S (that is, dim _H(S)=dim _P(S)) such that dim _H(S)>0, the Turing degree of S has constructive Hausdorff and packing dimension equal to 1. Finally, it is shown that no single Turing reduction can be a universal constructive Hausdorff dimension extractor, and that bounded Turing reductions cannot extract constructive Hausdorff dimension. We also exhibit sequences on which weak truth-table and bounded Turing reductions differ in their ability to extract dimension. F. Stephan was supported in part by NUS research grants Nos. R252-000-212-112 and R252-000-308-112.     

Algorithmically independent sequences

Two objects are independent if they do not affect each other. Independence is well-understood in classical information theory, but less in algorithmic information theory. Working in the framework of algorithmic information theory, the paper proposes two types of independence for arbitrary infinite binary sequences and studies their properties. Our two proposed notions of independence have some of the intuitive properties that one naturally expects. For example, for every sequence x, the set of sequences that are independent with x has measure one. For both notions of independence we investigate to what extent pairs of independent sequences, can be effectively constructed via Turing reductions (from one or more input sequences). In this respect, we prove several impossibility results. For example, it is shown that there is no effective way of producing from an arbitrary sequence with positive constructive Hausdorff dimension two sequences that are independent (even in the weaker type of independence) and have super-logarithmic complexity. Finally, a few conjectures and open questions are discussed.     

Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets

We study constructive and resource-bounded scaled dimension as an information content measure and obtain several results that parallel previous work on unscaled dimension. Scaled dimension for finite strings is developed and shown to be closely related to Kolmogorov complexity. The scaled dimension of an infinite sequence is characterized by the scaled dimensions of its prefixes. We obtain an exact Kolmogorov complexity characterization of scaled dimension. Juedes and Lutz (Inf. Comput. 125(1), 13–31, 1996) established a small span theorem for P/poly-Turing reductions which asserts that for any problem A in ESPACE, either the class of problems reducible to A (the lower span) or the class of problems to which A is reducible (the upper span) has measure 0 in ESPACE. We apply our Kolmogorov complexity characterization to improve this to (?3)rd-order scaled dimension 0 in ESPACE. As a consequence we obtain a new upper bound on the Kolmogorov complexity of Turing-hard sets for ESPACE.     

Effective dimensions and relative frequencies

Consider the problem of calculating the fractal dimension of a set X consisting of all infinite sequences S over a finite alphabet Σ that satisfy some given condition P on the asymptotic frequencies with which various symbols from Σ appear in S. Solutions to this problem are known in cases where

(i)

the fractal dimension is classical Hausdorff or packing dimension (by work of Volkmann and Olsen), or

(ii)

the fractal dimension is effective (even finite-state) and the condition Pcompletely specifies an empirical distribution π over Σ, i.e., a limiting frequency of occurrence for every symbol in Σ.

In this paper, we show how to calculate the finite-state dimension (equivalently, the finite-state compressibility) of such a set X when the condition P only imposes partial constraints on the limiting frequencies of symbols. Our results automatically extend to less restrictive effective fractal dimensions (e.g., polynomial-time, computable, and constructive dimensions), and they have the classical results (i) as immediate corollaries. Our methods are nevertheless elementary and, in most cases, simpler than those by which the classical results were obtained.     

On the power of generalized Mod-classes

We investigate the computational power of the new counting class ModP which generalizes the classes Mod _p P,p prime. We show that ModP is polynomialtime truth-table equivalent in power to #P and that ModP is contained in the class AmpMP. As a consequence, the classes PP, ModP, and AmpMP are all Turing equivalent, and thus AmpMP and ModP are not low for MP unless the counting hierarchy collapses to MP. Furthermore, we show that every set in C=P is reducible to some set in ModP via a random many-one reduction that uses only logarithmically many random bits. Hence, ModP and AmpMP are not closed under polynomial-time conjunctive reductions unless the counting hierarchy collapses.     

Extracting Kolmogorov complexity with applications to dimension zero-one laws

We apply results on extracting randomness from independent sources to “extract” Kolmogorov complexity. For any α,?>0, given a string x with K(x)>α|x|, we show how to use a constant number of advice bits to efficiently compute another string y, |y|=Ω(|x|), with K(y)>(1-?)|y|. This result holds for both unbounded and space-bounded Kolmogorov complexity.We use the extraction procedure for space-bounded complexity to establish zero-one laws for the strong dimensions of complexity classes within ESPACE. The unbounded extraction procedure yields a zero-one law for the constructive strong dimensions of Turing degrees.     

Characteristics of discrete transfinite time Turing machine models: Halting times,stabilization times,and Normal Form theorems

We give an acount of the basic determinants of the courses of computation of the Infinite Time Turing Machine model of Hamkins and Kidder, a model of computation which allows for transfinitely many steps of computation, and therefore may accept and output infinite strings of bits. We provide, inter alia, a Normal form Theorem, and a characterisation of which ordinals start gaps in halting times of such machines.     

New hash functions and their use in authentication and set equality

In this paper we exhibit several new classes of hash functions with certain desirable properties, and introduce two novel applications for hashing which make use of these functions. One class contains a small number of functions, yet is almost universal₂. If the functions hash n-bit long names into m-bit indices, then specifying a member of the class requires only O((m + log₂log₂(n)) · log₂(n)) bits as compared to O(n) bits for earlier techniques. For long names, this is about a factor of m larger than the lower bound of m + log₂n ? log₂m bits. An application of this class is a provably secure authentication technique for sending messages over insecure lines. A second class of functions satisfies a much stronger property than universal₂. We present the application of testing sets for equality.The authentication technique allows the receiver to be certain that a message is genuine. An “enemy”—even one with infinite computer resources—cannot forge or modify a message without detection. The set equality technique allows operations including “add member to set,” “delete member from set” and “test two sets for equality” to be performed in expected constant time and with less than a specified probability of error.     

On Shortest Linear Recurrences

This is an expository account of a constructive theorem on the shortest linear recurrences of a finite sequence over an arbitrary integral domainR. A generalization of rational approximation, which we call “realization”, plays a key role throughout the paper.We also give the associated “minimal realization” algorithm, which has a simple control structure and is division-free. It is easy to show that the number ofR-multiplications required isO(n²), wherenis the length of the input sequence.Our approach is algebraic and independent of any particular application. We view a linear recurring sequence as a torsion element in a naturalR[X]-module. The standardR[X]-module of Laurent polynomials overRunderlies our approach to finite sequences. The prerequisites are nominal and we use short Fibonacci sequences as running examples.     

Maximal Pairs of Computably Enumerable Sets in the Computably Lipschitz Degrees

A set A is computably Lipschitz or cl-reducible, for short, to a set B if A is Turing reducible to B by an oracle Turing machine with use function ? such that ? is bounded by the identity function up to an additive constant, i.e., ?(n)??n+O(1). In this paper we study maximal pairs of computably enumerable (c.e.) cl-degrees or maximal pairs, for short, i.e., pairs of c.e. cl-degrees such that there is no c.e. cl-degree that is above both cl-degrees in this pair. Our main results are as follows. (1) A c.e. Turing degree contains a c.e. cl-degree that is half of a maximal pair if and only if this Turing degree contains a maximal pair if and only if this Turing degree is array noncomputable. (2) The cl-degrees of all weak truth-table complete sets are halves of maximal pairs while there is a Turing complete set A such that the cl-degree of A is not half of any maximal pair. In fact, any high c.e. Turing degree contains a c.e. cl-degree that is not half of a maximal pair. (3) Above any c.e. cl-degree there is a maximal pair. (4) There is a maximal pair which at the same time is a minimal pair. (5) There is a pair of c.e. cl-degrees that is not maximal and does not possess a least upper bound. Moreover, we make some observations on the structure of the c.e. cl-degrees in general. For instance, we give a very simple proof of the fact that there are no maximal c.e. cl-degrees.     

Turing degrees of reals of positive effective packing dimension

A relatively longstanding question in algorithmic randomness is Jan Reimann's question whether there is a Turing cone of broken dimension. That is, is there a real A such that contains no 1-random real, yet contains elements of nonzero effective Hausdorff dimension? We show that the answer is affirmative if Hausdorff dimension is replaced by its inner analogue packing dimension. We construct a minimal degree of effective packing dimension 1.This leads us to examine the Turing degrees of reals with positive effective packing dimension. Unlike effective Hausdorff dimension, this is a notion of complexity which is shared by both random and sufficiently generic reals. We provide a characterization of the c.e. array noncomputable degrees in terms of effective packing dimension.     

How Powerful Are Integer-Valued Martingales?

In the theory of algorithmic randomness, one of the central notions is that of computable randomness. An infinite binary sequence?X is computably random if no recursive martingale (strategy) can win an infinite amount of money by betting on the values of the bits of?X. In the classical model, the martingales considered are real-valued, that is, the bets made by the martingale can be arbitrary real numbers. In this paper, we investigate a more restricted model, where only integer-valued martingales are considered, and we study the class of random sequences induced by this model.     

The Parameterized Complexity of Stabbing Rectangles

The NP-complete geometric covering problem Rectangle Stabbing is defined as follows: Given a set R of axis-parallel rectangles in the plane, a set L of horizontal and vertical lines in the plane, and a positive integer k, select at most k of the lines such that every rectangle is intersected by at least one of the selected lines. While it is known that the problem can be approximated in polynomial time within a factor of two, its parameterized complexity with respect to the parameter k was open so far. Giving two fixed-parameter reductions, one from the W[1]-complete problem Multicolored Clique and one to the W[1]-complete problem Short Turing Machine Acceptance, we prove that Rectangle Stabbing is W[1]-complete with respect to the parameter k, which in particular means that there is no hope for an algorithm running in f(k)?|R∪L| ^O(1) time. Our reductions also show the W[1]-completeness of the more general problem Set Cover on instances that “almost have the consecutive-ones property”, that is, on instances whose matrix representation has at most two blocks of 1s per row. We also show that the special case of Rectangle Stabbing where all rectangles are squares of the same size is W[1]-hard. The case where the input consists of non-overlapping rectangles was open for some time and has recently been shown to be fixed-parameter tractable (Heggernes et al., Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009). By giving an algorithm running in (2k) ^k ?|R∪L| ^O(1) time, we show that Rectangle Stabbing is fixed-parameter tractable in the still NP-hard case where both these restrictions apply, that is, in the case of disjoint squares of the same size. This algorithm is faster than the one in Heggernes et al. (Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009) for the disjoint rectangles case. Moreover, we show fixed-parameter tractability for the restrictions where the rectangles have bounded width or height or where each horizontal line intersects only a bounded number of rectangles.     

Fully Dynamic Geometric Spanners

In this paper we present an algorithm for maintaining a spanner over a dynamic set of points in constant doubling dimension metric spaces. For a set S of points in ? ^d , a t-spanner is a sparse graph on the points of S such that there is a path in the spanner between any pair of points whose total length is at most t times the distance between the points. We present the first fully dynamic algorithm for maintaining a spanner whose update time depends solely on the number of points in S. In particular, we show how to maintain a (1+ε)-spanner with O(n/ε ^d ) edges, where points can be inserted to S in an amortized update time of O(log?n) and deleted from S in an amortized update time of $\tilde{O}(n^{1/3})$ . As a by-product of our techniques we obtain a simple incremental algorithm for constructing a (1+ε)-spanner with O(n/ε ^d ) edges in constant doubling dimension metric spaces whose running time is O(nlog?n).     

Generation of Random Digital Simple Curves with Artistic Emulation

This paper presents two novel interdependent techniques for random digital simple curve generation. The first one is about generating a curve of finite length, producing a sequence of points defining a digital path ρ ‘on the fly’. The second is for the creation of artistic sketches from line drawings and edge maps, using multiple instances of such random digital paths. A generated digital path ρ never intersects or touches itself, and hence becomes simple and irreducible. This is ensured by detecting every possible trap formed by the previously generated part of ρ, which, if entered into, cannot be exited without touching or intersecting ρ. The algorithm is completely free of any backtracking and its time complexity is linear in the length of ρ. For artistic emulation, a curve-constrained domain is defined by the Minkowski sum of the input drawing with a structuring element whose size varies with the pencil diameter. An artist’s usual trait of making irregular strokes and sub-strokes, with varying shades while sketching, is thus captured in a realistic manner. Algorithmic solutions of non-photorealism are perceived as an enrichment of contemporary digital art. Simulation results for the presented algorithms have been furnished to demonstrate their efficiency and elegance.     

Time-Bounded Kolmogorov Complexity and Solovay Functions

A Solovay function is an upper bound g for prefix-free Kolmogorov complexity K that is nontrivial in the sense that g agrees with K, up to some additive constant, on infinitely many places n. We obtain natural examples of computable Solovay functions by showing that for some constant c ₀ and all computable functions t such that c ₀ n??t(n), the time-bounded version K ^t of K is a Solovay function. By unifying results of Bienvenu and Downey and of Miller, we show that a right-computable upper bound g of K is a Solovay function if and only if ?? _g =??2^?g(n) is Martin-Löf random. We obtain as a corollary that the Martin-Löf randomness of the various variants of Chaitin??s ?? extends to the time-bounded case in so far as $\Omega _{ \textnormal{K}^{t}}$ is Martin-Löf random for any t as above. As a step in the direction of a characterization of K-triviality in terms of jump-traceability, we demonstrate that a set A is K-trivial if and only if A is O(g(n)?K(n))-jump traceable for all computable Solovay functions g. Furthermore, this equivalence remains true when the universal quantification over all computable Solovay functions in the second statement is restricted either to all functions of the form K ^t for some function t as above or to a single function K ^t of this form. Finally, we investigate into the plain Kolmogorov complexity C and its time-bounded variant C ^t of initial segments of computably enumerable sets. Our main theorem here asserts that every high c.e. Turing degree contains a c.e. set B such that for any computable function t there is a constant c _t >0 such that for all m it holds that C ^t (B?m)??c _t ?m, whereas for any nonhigh c.e. set A there is a computable time bound t and a constant c such that for infinitely many m it holds that C ^t (A?m)??logm+c. By similar methods it can be shown that any high degree contains a set B such that C ^t (B?m)??⁺ m/4. The constructed sets B have low unbounded but high time-bounded Kolmogorov complexity, and accordingly we obtain an alternative proof of the result due to Juedes et al. (Theor. Comput. Sci. 132(1?C2):37?C70, 1994) that every high degree contains a strongly deep set.     

Decision algorithms for multiplayer noncooperative games of incomplete information

Extending the complexity results of Reif [1,2] for two player games of incomplete information, this paper (see also [3]) presents algorithms for deciding the outcome for various classes of multiplayer games of incomplete information, i.e., deciding whether or not a team has a winning strategy for a particular game. Our companion paper, [4] shows that these algorithms are indeed asymptotically optimal by providing matching lower bounds. The classes of games to which our algorithms are applicable include games which were not previously known to be decidable. We apply our algorithms to provide alternative upper bounds, and new time-space trade-offs on the complexity of multiperson alternating Turing machines [3]. We analyze the algorithms to characterize the space complexity of multiplayer games in terms of the complexity of deterministic computation on Turing machines.In hierarchical multiplayer games, each additional clique (subset of players with the same information) increases the complexity of the outcome problem by a further exponential. We show that an S(n) space bounded k-player game of incomplete information has a deterministic time upper bound of k + 1 repeated exponentials of S(n). Furthermore, S(n) space bounded k-player blindfold games have a deterministic space upper bound of k repeated exponentials of S(n). This paper proves that this exponential blow-up can occur.We also show that time bounded games do not exhibit such hierarchy. A T(n) time bounded blindfold multiplayer game, as well as a T(n) time bounded multiplayer game of incomplete information, has a deterministic space bound of T(n).     

QEST nD: n-dimensional extension and generalisation of a software performance measurement model

Process and product measurement is one of the key topics in the Software Engineering field. There already exists a significant number of one-dimensional (1D) models of performance, which integrate all individual measurements into a single performance index. However, these types of models are too over-simplified to adequately reflect the multi-dimensional nature of performance. Similarly, 1D models do not meet the analytical requirements of management when various ‘viewpoints’ must be taken into account simultaneously. This papers proposes a multi-dimensional measurement model capable of handling, concurrently, distinct but related areas of interest, each representing a dimension of performance.The proposed model is based on an open model called Quality factor+Economic, Social and Technical dimensions (QEST) which had been developed to handle, simultaneously and concurrently, a three-dimensional perspective of performance:

• •economic dimension—the perspective of managers;
• •social dimension—the perspective of users;
• •technical dimension—the perspective of developers.

A more generic form of this model has been developed to handle a greater number of perspectives, as required by, for instance, several Performance Management frameworks such as the Balanced Scorecard, the Intangible Asset Monitor and the Skandia Navigator. This paper presents the generic form derived from the QEST model, referred to as QEST nD, with the ability to handle n possible dimensions. The generic model is also verified for the particular case of three dimensions using sample data previously applied to the original QEST software performance model.     

An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs has attracted many research efforts, mainly due to its interesting structure and its numerous applications, especially in DNA sequence analysis and resource allocation, among others. In one of the most natural generalizations of tolerance graphs, namely multitolerance graphs, two tolerances are allowed for each interval—one from the left and one from the right side of the interval. Then, in its interior part, every interval tolerates the intersection with others by an amount that is a convex combination of its two border-tolerances. In the comparison of DNA sequences between different organisms, the natural interpretation of this model lies on the fact that, in some applications, we may want to treat several parts of the genomic sequences differently. That is, we may want to be more tolerant at some parts of the sequences than at others. These two tolerances for every interval—together with their convex hull—define an infinite number of the so called tolerance-intervals, which make the multitolerance model inconvenient to cope with. In this article we introduce the first non-trivial intersection model for multitolerance graphs, given by objects in the 3-dimensional space called trapezoepipeds. Apart from being important on its own, this new intersection model proves to be a powerful tool for designing efficient algorithms. Given a multitolerance graph with n vertices and m edges along with a multitolerance representation, we present algorithms that compute a minimum coloring and a maximum clique in optimal O(nlogn) time, and a maximum weight independent set in O(m+nlogn) time. Moreover, our results imply an optimal O(nlogn) time algorithm for the maximum weight independent set problem on tolerance graphs, thus closing the complexity gap for this problem. Additionally, by exploiting more the new 3D-intersection model, we completely classify multitolerance graphs in the hierarchy of perfect graphs. The resulting hierarchy of classes of perfect graphs is complete, i.e. all inclusions are strict.