Search

This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A "translational" method which escapes some of the limitations of earlier approaches leads to a refinement of the established hierarchy. The previous complexity classes are shown to possess certain translational properties. An related hierarchy of complexity classes of monotonic functions is examined

A programming language for the partial computable functionals is used as the basis for a definition of the computational complexity of functionals (type2 functions). An axiomatic account in the spirit of Blum is then provided. The novel features of this approach are justified by applying it to problems in abstract complexity, specifically operator speed-up, and by using it to define the illusive notion of the polynomial degree of an arbitrary function. New results are obtained for these degrees.

We consider the extent to which it's possible, given 8 program p for computing a function, f, to Find an optimal program p' which also computes f and is either provably equivalent to p or else provably an optimal program. Our methods and problems come chiefly from abstract recurslontheoretic complexity theory, but some of our results may be viewed as directly challenging the intuitive interpretatIon of earlier results In the area.

It is proven that complexity classes of abstract measures of complexity need not be recursively enumerable. However, the complement of each class is r.e. Properties of effective enumerations of complexity classes are studied. For any measure there is another measure with 'almost' the same complexity classes such that almost every class admits an effective enumeration in terms of speedy devices. Finally complexity classes are shown to not be closed under intersection.

This paper studies possible extensions of the concept of complexity class of recursive functions to partial recursive functions. Many of the well-known results for total complexity classes are shown to have corresponding, though not exactly identical, statements for partial classes. In particular, with two important exceptions, all results on the presentation and decision problems of membership for the two most reasonable definitions of partial classes are the same as for total classes. The exceptions concern presentations of the complements and maximum difficulty for decision problems of the more restricted form of partial classes. The last section of this paper shows that it is not possible to have an “Intersection Theorem”, corresponding to the Union Theorem of McCreight and Meyer, either for complexity classes or complexity index sets.

The study of Computational Complexity began with the investigation of Turing machine computations with limits on the amounts of tape or time which could be used. Latter a set of general axioms for measures of resource limiting was presented and this instigated much study of the properties of these general measures. Many interesting results were shown, but the general axioms allowed measures with undesirable properties and many attempts have been made to tighten up the axioms so that only desirable measures will be defined. In this paper several undecidability aspects of complexity classes and several sets associated with them will be examined. These sets will be classified by their degree of unsolvability and restrictions will be placed on measures so that these degrees are identical. This gives rise to a new criterion for the “naturalness” of measures and to suggestions for strengthening the measures of complexity.

The complexity closure of a computable function is defined by a set of axioms. The axioms are satisfied by complexity classes that are computation time closed and also by other complexity classes which do not have this property. It is then shown that there exist honest recursive functions whose complexity closure are setwise incomparable. Further that there exist chains of honest recursive functions whose complexity closures are densely ordered under set inclusion.

This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A "translational" method which escapes some of the limitations of earlier approaches leads to a refinement of the established hierarchy. The previous complexity classes are shown to possess certain translational properties. An related hierarchy of complexity classes of monotonic functions is examined

This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A "translational" method which escapes some of the limitations of earlier approaches leads to a refinement of the established hierarchy. The previous complexity classes are shown to possess certain translational properties. An related hierarchy of complexity classes of monotonic functions is examined

The initial ideas regarding measuring complexity appeared in computer science, with the concept of computational algorithms. As a consequence, the equivalence between algorithm complexity and informational entropy was shown. Attempting to connect these abstract formalisms to natural phenomena, described by Thermodynamics, the maximum disorder of a system would correspond to maximum complexity, a fact incoherent with the intuitive ideas of natural complexity. Considering that natural complexity resides in the half path between order and disorder, Lopez-Ruiz, Mancini and Calbet proposed a definition for complexity, which is referred as LMC measure. Shiner, Davison and Landsberg, by slightly changing the definition of LMC, proposed the SDL measure. However, there are some situations where complexity is more associated to order than to disorder and vice-versa. Here, a computational study concerning weighting order and disorder in LMC and SDL measures is presented, by using a binomial probability distribution as reference, showing the qualitative equivalence between them and how the weight changes complexity.

We show that deterministic communication complexity can be super logarithmic in the partition number of the associated communication matrix. We also obtain near-optimal deterministic lower bounds for the Clique vs. Independent Set problem, which in particular yields new lower bounds for the log-rank conjecture. All these results follow from a simple adaptation of a communication-to-query simulation theorem of Raz and McKenzie (Combinatorica 1999) together with lower bounds for the analogous query complexity questions.

The often observed complexity gap between the expressiveness of a logical formalism and its exponentially harder expression complexity is proven for all logical formalisms which satisfy natural closure conditions. The expression complexity of the prefix classes of second-order logic can thus be located in the corresponding classes of the weak exponential hierarchies; further results about expression complexity in database theory, logic programming, nonmonotonic reasoning, first-order logic with Henkin quantifiers and default logic are concluded. The proof method illustrates the significance of quantifier-free interpretations in descriptive complexity theory.

In this paper, we look at synchronization over a finite window of data from a computational complexity point of view. The setting is purely in discrete time. It is shown that for polynomial systems the computational complexity of a readily available global Newton algorithm adapted to identify the finite trajectory of the dynamical system's state over the observation window scales in a polynomial manner in the dimension of the system state and the degree of the polynomials required to describe the models. Moreover, this algorithm has good robustness properties with respect to measurement errors and model errors. Simulation results are included.

Black-box complexity measures the difficulty of classes of functions with respect to optimisation by black-box algorithms. Comparing the black-box complexity with the worst case performance of a best know randomised search heuristic can help to assess if the randomised search heuristic is efficient or if there is room for improvement. When considering an example function it is necessary to extend it to a class of functions since single functions always have black-box complexity 1. Different kinds of extensions of single functions to function classes have been considered. In cases where the gap between the performance of the best randomised search heuristic and the black-box complexity is still large it can help to consider more restricted black-box complexity notions like unbiased black-box complexity. For the well-known Jump function neither considering different extensions nor considering more restricted notions of black-box complexity have been successful so far. We argue that the problem is not with the notion of black-box complexity but with the extension to a function class. We propose a different extension and show that for this extension there is a much better agreement even between the performance of an extremely simple evolutionary algorithm and the most general notion of black-box complexity.

In a variety of PAC learning models, a trade-off between time and information seems to exist: with unlimited time, a small amount of information suffices, but with time restrictions, more information sometimes seems to be required. In addition, it has long been known that there are concept classes that can be learned in the absence of computational restrictions, but (under standard cryptographic assumptions) cannot be learned in polynomial time (regardless of sample size). Yet, these results do not answer the question of whether there are classes for which learning from a small set of examples is computationally infeasible, but becomes feasible when the learner has access to (polynomially) more examples. To address this question, we introduce a new measure of learning complexity called computational sample complexity that represents the number of examples sufficient for polynomial time learning with respect to a fixed distribution. We then show concept classes that (under similar cryptographic assumptions) possess arbitrarily sized gaps between their standard (information-theoretic) sample complexity and their computational sample complexity. We also demonstrate such gaps for learning from membership queries and learning from noisy examples.

The /spl beta/ hierarchy consists of sets /spl betasub k/=NP[log/sup k/ n]/spl sube/NP. Unlike collapses in the polynomial hierarchy and the Boolean hierarchy, collapses in the /spl beta/ hierarchy do not seem to translate up, nor does closure under complement seem to cause the hierarchy to collapse. For any consistent set of collapses and separations of levels of the hierarchy that respects P=/spl betasub 1spl subespl betasub 2spl sube/.../spl sube/NP, we can construct an oracle relative to which those collapses and separations hold, yet any (or all) of the /spl betasub k/'s are closed under complement. We give a few relatively tame examples: first, for any k/spl ges/1, we construct an oracle relative to which P=/spl betasub kspl nespl betasub k+1spl nespl betasub k+2spl ne/..., and then another oracle relative to which P=/spl betasub kspl nespl betasub k+1/=PSPACE. We also construct an oracle relative to which /spl betasub 2k/=/spl betasub 2k+1spl nespl betasub 2k+2/ for all k. These results hold for more general nondeterminism hierarchies within NP, although they are in sharp contrast to the upward collapse results for Buss and Goldsmith's (1993) nondeterminism hierarchy in P. >

In this paper we investigate the communication and cooperation phenomenon in Cooperating Distributed Grammar Systems (henceforth CDGSs). In this respect, we define several complexity structures and two complexity measures, the cooperation and communication complexity measures. These measures are studied with respect to the derivation modes and fairness conditions under which CDGSs may work. We deal with trade-offs between time, space, cooperation, and communication complexity of languages generated by CDGSs with regular, linear, and context-free components. Cooperation and communication processes in CDGSs with regular and linear components are of equal complexity. The two (equal) cooperation and communication complexity measures are either constant or linear, as functions of lengths of words in the generated language. The same result holds for the cooperation and communication complexity of q-fair languages generated by CDGSs with regular and linear components. For the case of non-constant communication (cooperation) the time and space used by a nondeterministic multitape Turing machine to recognize weakly q-fair languages are linear, as is the communication (cooperation) complexity. For CDGSs with context-free components the cooperation and communication complexity may be different. These measures are either linear or logarithmic functions, in terms of lengths of words in the generated language. In order to find trade-offs between time, space, cooperation, and communication complexity of languages generated by CDGSs with context-free components we study asymptotic behavior of growth functions characteristic to these measures. We prove that languages generated by CDGSs with context-free components are accepted by nondeterministic multitape Turing machines either in quadratic time, linear space, and with cooperation complexity that varies from logarithmic to linear, or in polynomial or exponential time and space, and linear cooperation complexity.

A definition of self-reducibility is proposed to deal with logarithmic space complexity classes. A general property derived from the definition is used to prove known results comparing uniform and nonuniform complexity classes below polynomial time, and to obtain novel ones regarding nondeterministic nonuniform classes and reducibility to context-free languages.

Complexity classes are usually defined by referring to computation models and by putting suitable restrictions on them. Following this approach, many proofs of results are tightly bound to the characteristics of the computation model and of its restrictions and therefore they sometimes hide the essential properties which ensure the obtained results. In order to obtain more general results, a uniform family of computation models which encompass most of the complexity classes of interest has been introduced in an earlier paper. As an initial set of results derivable from the proposed approach, a necessary and sufficient condition to prove the separation of relativized complexity classes, a characterization of complexity classes which admit a complete language, and a sufficient condition to prove the strong separation of relativized complexity classes have been presented in that paper. In this paper, we apply this approach to obtain positive relativization results, that is, results similar to those obtained in the literature. In particular, our goal is to prove statements of the kind: "Given two complexity classes C and D, C = D if and only if for every sparse set S, CS = DS." We derive a sufficient condition to prove such results and, as an application, we prove a general theorem from which all of the results obtained previously and new ones can be immediately derived.

We present a new formulation of the Mastrovito multiplication matrix for the field GF(2/sup m/) generated by an arbitrary irreducible polynomial. We study in detail several specific types of irreducible polynomials, e.g., trinomials, all-one-polynomials, and equally-spaced-polynomials, and obtain the time and space complexity of these designs. Particular examples illustrating the properties of the proposed architecture are also given. The complexity results established in this paper match the best complexity results known to date. The most important new result is the space complexity of the Mastrovito multiplier for an equally-spaced-polynomial, which is found as (m/sup 2/-/spl Delta/) XOR gates and m/sup 2/ AND gates, where /spl Delta/ is the spacing factor.

We propose a new inductive principle, which we call the complexity approximation principle (CAP). This principle is a natural generalization of Rissanen’s minimum description length (MDL) principle and Wallace’s minimum message length (MML) principle and is based on the notion of predictive complexity, a recent generalization of Kolmogorov complexity. Like the MDL principle, CAP can be regarded as an implementation of Occam’s razor.

Throughout the development of finite model theory, the fragments of firstorder logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area. For each k > 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k (free or bound) variables. The logics Lk are the simplest finite-variable logics. Later, we are going to consider infinitary variants and extensions by so-called counting quantifiers. Finite variable logics have mostly been studied on finite structures. Like the whole area of finite model theory, they have interesting model theoretic, complexity theoretic, and combinatorial aspects. For finite structures, first-order logic is often too expressive, since each finite structure can be characterized up to isomorphism by a single first-order sentence, and each class of finite structures that is closed under isomorphism can be characterized by a first-order theory. The finite variable fragments seem to be promising candidates with the right balance between expressive power and weakness for a model theory of finite structures. This may have motivated Poizat [67] to collect some basic model theoretic properties of the Lk. Around the same time Immerman [45] showed that important complexity classes such as polynomial time (PTIME) or polynomial space (PSPACE) can be characterized as collections of all classes of (ordered) finite structures definable by uniform sequences of first-order formulas with a fixed number of variables and varying quantifier-depth. Although these early results from descriptive complexity theory have been put in much more elegant forms later using so-called fixed-point logics, the importance of the number of variables as a complexity measure remained. In 1990, Kolaitis and Vardi [52] proved a 0-1 law for the infinitary finite variable logics. As a corollary, they re-proved a result of Blass, Gurevich, and Kozen [7] that there is a 0-1 law for least-fixed point logic. The fact that makes Kolaitis' and Vardi's paper so remarkable is that it uses finite variable logics as a technical tool to obtain results concerning fixed-point logics, which are

Results by Toda (1991), Vinay (1991), Damm (1991), and Valiant (1992) have shown that the complexity of the determinant is characterized by the complexity of counting the number of accepting computations of a nondeterministic logspace-bounded machine. (This class of functions is known as L.) By using that characterization and by establishing a few elementary closure properties, we give a very simple proof of a theorem of Jung (1985), showing that probabilistic logspace-bounded (PL) machines lose none of their computational power if they are restricted to run in polynomial time. We also present new results comparing and contrasting the classes of functions reducible to PL, #L, and the determinant, using various notions of reducibility. >

The classes of computable functions defined by a bound on the computation time are shown not to be closed under infinite descending intersection.

Given any simply consistent formal theory F of the state complexity L(S) of finite binary sequences S as computed by 3-tape-symbol Turing machines, there exists a natural number L(F) such that L(S) > n is provable in F only if n < L(F). On the other hand, almost all finite binary sequences S satisfy L(S) < L(F). The proof resembles Berry's paradox, not the Epimenides nor Richard paradoxes.

This report concerns some of the elementary concepts in complexity theory. In particular, a mathematical model is developed for a finite-state machine and the Turing machine. This model has applications to public key cryptosystems, in determining which problems are P, NP, or NPC. The report was written to be as accessible to the nonspecialist as possible.

Recently there has been a great deal of study of measures of computational complexity. In light of the results of Blum [1] yielding speedup theorems for abstract complexity measures, and the lack of any general agreement as to reasonable complexity measures, there is reason to study even artificial complexity measures, such as the number of tape reversals on a one-tape Turing machine, which lack intuitive appeal but do lead to some amusing results. The present paper, which should be read in connection with [2], provides the usual Hartmanis-Stearnstype speedup theorem [3] for off-line one-tape Turing machines; namely, the appropriate reversal complexity classes associated with f(x) and cf(x) are the same for any constant c>0. The proofs are based on straightforward applications of the notion of crossing sequences [4].

Perhaps the two most basic phenomena discovered by the recent application of recursion theoretic methods to the developing theories of computational complexity have been Blum's speed-up phenomena, with its extension to operator speed-up by Meyer and Fischer, and the Borodin gap phenomena, with its extension to operator gaps by Constable. In this paper we present a proof of the operator gap theorem which is much simpler than Constable's proof. We also present an improved proof of the Blum speed-up theorem which has a straightforward generalization to obtain operator speed-ups. The proofs of this paper are new; the results are not. The proofs themselves are entirely elementary: we have eliminated all priority mechanisms and all but the most transparent appeals to the recursion theorem. Even these latter appeals can be eliminated in some "reasonable" complexity measures. Imnplicit in the proofs is what we believe to be a new method for viewing the construction of "complexity sequences." Unspecified notation follows Rogers [12]. 2iqi is any standard indexing of the partial recursive functions. N is the set of all nonnegative integers. 2iDi is a canonical indexing of all finite subsets of N: from i we can list Di and know when the listing is completed. Similarly, 2iFi is a canonical indexing of all finite functions defined (exactly) on some initial segment {0, 1, 2, , n}. ;,D, is any Blum measure of computational complexity or resource. Specifically, for all i, domain (Di= domain Xi, and the ternary relation (Pi(x)