In this paper we deal with the logical description of complexity classes arising in the real number model of computation introduced by Blum, Shub, and Smale [4]. We adapt the approach of descriptive complexity theory for this model developped in [14] and extend it to capture some further complexity classes over the reals by logical means. Among the latter we find NC R , PAR R , EXP R and some others more.

We consider the problem of obtaining logical characterisations of oracle complexity classes. In particular, we consider the complexity classes LOGSPACENP and PTIMENP. For these classes, characterisations are known in terms of NP computable Lindström quantifiers which hold on ordered structures. We show that these characterisations are unlikely to extend to arbitrary structures, since this would imply the collapse of certain exponential complexity hierarchies. We also observe, however, that PTIMENP can be characterised in terms of (...) Lindström quantifers , though it remains open whether this can be done for LOGSPACENP. (shrink)

The set, the closure of F, is the closure with respect to substitution and concatenation recursion on notation of a set of basic functions comprehending the set F. By improving earlier work, we show that is the substitution closure of a simple function set and characterize well‐known function complexity classes as the substitution closure of finite sets of simple functions.

It is known that for two given countable sets of unary relations A and B on ω there exists an infinite set H ⫅ ω on which A and B are the same. This result can be used to generate counterexamples in expressibility theory. We examine the sharpness of this result.

We prove two sets of results concerning computational complexity classes. First, we propose a new variation of the random oracle hypothesis, originally posed by Bennett and Gill after they showed that relative to a randomly chosen oracle, with probability 1. Their original hypothesis was quickly disproven in several ways, most famously in 1992 with the result that, in spite of the classes being shown unequal with probability 1. Here we propose a variation of what it means to (...) be “large” using the Ellentuck topology. In this new context, we demonstrate that the set of oracles separating and is not small, and obtain similar results for the separation of from along with the separation of from. We also show that the set of oracles equating with is large in this new sense. We demonstrate that this version of the hypothesis provides a sufficient condition for unrelativized relationships, at least in the cases considered here. Second, we examine the descriptive complexity of the classes of oracles providing the separations for these various classes, and determine their exact placement in the Borel hierarchy. (shrink)

We study some representations of real numbers. We compare these representations, on the one hand from the viewpoint of recursive functionals, and of complexity on the other hand.The impossibility of obtaining some functions as recursive functionals is, in general, easy. This impossibility may often be explicited in terms of complexity: - existence of a sequence of low complexity whose image is not a recursive sequence, - existence of objects of low complexity but whose images have arbitrarily (...) high time- complexity .Moreover, some representations of real numbers that are equivalent from the viewpoint of recursive functionals, are very distinct from the viewpoint of complexity.We make a particular study of representations via continued fractions . We precise exactly what part of information available in the x's dfc is equivalent to the information available in its Dedekinds cut. We show that the sum of two reals whose dfcs are polynomial-time computable may be a real whose dfc has time complexity arbitrarily high.This work confirms that the unique representation of real numbers suitable for the ordinary calculus is via explicit Cauchy sequences of rationals.RésuméNous étudions différentes manières de présenter les nombres réels. Nous comparons ces présentations du point de vue des fonctionnelles récursives d'une part, et de celui des classes de complexité d'autre part.L'impossibilité d'obtenir certaines fonctions sous forme de fonctionnelles récursives est en général facile à établir. Cette impossiblité peut souvent être explicitée en termes de complexité: - il existe une suite de faible complexité dont l'image est une suite non récursive, - il existe des objets de faible complexité mais dont les images sont des objets de complexité arbitrairement grande .En outre, certaines présentations des réels équivalentes du point de vue des fonctionnelles récursives se distinguent nettement du point de vue de la complexité.Nous faisons une étude particulière concernant les développements en fraction continue . Nous précisions exactement quelle est la partie de l'information disponible dans le dfc d'un réel x qui équivaut à l'information disponible dans sa coupure de Dedekind. Nous montrons également que la somme de deux réels dont le dfc est calculable en temps polynomial peut être un réel dont le dfc est de complexité arbitrairement grande.Ce travail confirme que seule une présentation des réels via des suites de rationnels explicitement de Cauchy est adaptée aux calculs avec les réels. (shrink)

We use the category of presheaves over PTIME-functions in order to show that Cook and Urquhart's higher-order function algebra PV ω defines exactly the PTIME-functions. As a byproduct we obtain a syntax-free generalisation of PTIME-computability to higher types. By restricting to sheaves for a suitable topology we obtain a model for intuitionistic predicate logic with ∑ 1 b -induction over PV ω and use this to re-establish that the provably total functions in this system are polynomial time computable. Finally, we (...) apply the category-theoretic approach to a new higher-order extension of Bellantoni-Cook's system BC of safe recursion. (shrink)

An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a Π₁⁰ class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y⊆ω there is an X in P such that X≥wtt Y. We show that this is also equivalent to the Π₁⁰ class's being large in some sense. We (...) give an example of how this result can be used in the study of scattered linear orders. (shrink)

Aleksandar Ignjatović. Delineating Classes of Computational Complexity via Second Order Theories with Weak Set Existence Principles (I).

A class K of structures is controlled if for all cardinals λ, the relation of L∞,λ-equivalence partitions K into a set of equivalence classes . We prove that no pseudo-elementary class with the independence property is controlled. By contrast, there is a pseudo-elementary class with the strict order property that is controlled 69–88).

The transition to twenty-first century post-industrial capitalism from the 'welfare' industrial capitalism of the twentieth century, has affected the ways in which class is lived in terms of relational inequality and the factors that structure identity. Class After Industry takes a complex realist approach to the dynamics of individual lives, places, the social structure and analyses their significance in terms of class. A wide range of quantitative and qualitative studies are drawn on to explore how 'life after industry' shapes class, (...) and the consequent potential for social change. The book will be of interest across the social sciences and beyond, to those concerned with how class forms might translate into political action. (shrink)

Zermelo, Frege and Russell accepted a common theme regarding classes. Classes were determined by other entities—functions, concepts, properties or conditions—and a class was only acceptable in the theory if there was such a determining entity. Thus, the existence of a class was taken to be dependent on a concept, function, condition, etc. whose satisfaction or fulfillment by an element determined the element to be a member of the class. This feature was behind Russell’s “no class theory,” where a (...) class was not only taken to be “determined by” a function but was considered to be “replaceable” by its determining function, as well as Frege’s problematic claim that every concept determined a class. Thus, Russell could identify the class of φs with, and Frege could take there to be a class of φs whose elements were all things falling under φ. Treating classes in such a manner does not provide for an adequate ontological assay of classes. If classes are entities, then whether or not there exists a class cannot depend on there being a property or function or concept or condition specifying membership in the class. Such a concept or property merely allows us to provide a definite description of the class. It is not the basis for the existence of the class. Russell’s “no class” theory of the first edition of Principia takes class abstracts and the classes they purportedly denote as “incomplete symbols.” As applied to the class abstract signs, the notion of an “incomplete symbol” means that such signs are only meaningful in contexts, in fact, are contextually defined. Thus, their meaning is not supplied by an entity such a sign purportedly denotes. As applied to a purported entity, to say of such a “thing” that it is an incomplete symbol is to say that it doesn’t exist. Thus, Russell classified the King of France in 1905, the king, as well as the definite description, as an incomplete symbol and called propositions “incomplete symbols” when he denied that there were such entities. (shrink)

Let$ \le _c $be computable the reducibility on computably enumerable equivalence relations. We show that for every ceerRwith infinitely many equivalence classes, the index sets$\left\{ {i:R_i \le _c R} \right\}$,$\left\{ {i:R_i \ge _c R} \right\}$, and$\left\{ {i:R_i \equiv _c R} \right\}$are${\rm{\Sigma }}_3^0$complete, whereas in caseRhas only finitely many equivalence classes, we have that$\left\{ {i:R_i \le _c R} \right\}$is${\rm{\Pi }}_2^0$complete, and$\left\{ {i:R \ge _c R} \right\}$ is${\rm{\Sigma }}_2^0$complete. Next, solving an open problem from [1], we prove that the index (...) set of the effectively inseparable ceers is${\rm{\Pi }}_4^0$complete. Finally, we prove that the 1-reducibility preordering on c.e. sets is a${\rm{\Sigma }}_3^0$complete preordering relation, a fact that is used to show that the preordering relation$ \le _c $on ceers is a${\rm{\Sigma }}_3^0$complete preordering relation. (shrink)

We prove that the homeomorphism relation between compact spaces can be continuously reduced to the homeomorphism equivalence relation between absolute retracts, which strengthens and simplifies recent results of Chang and Gao, and Cieśla. It follows then that the homeomorphism relation of absolute retracts is Borel bireducible with the universal orbit equivalence relation. We also prove that the homeomorphism relation between regular continua is classifiable by countable structures and hence it is Borel bireducible with the universal orbit equivalence relation of the (...) permutation group on a countable set. On the other hand we prove that the homeomorphism relation between rim-finite metrizable compacta is not classifiable by countable structures. (shrink)

In the basic modal language and in the basic modal language with the added universal modality, first-order definability of all formulas over the class of all frames is shown. Also, it is shown that the problems of modal definability of first-order sentences over the class of all frames in the languages and are both PSPACE-complete.

Let X be a non-reflexive Banach space such that X ∗ is separable. Let N be the set of all equivalent norms on X , equipped with the topology of uniform convergence on bounded subsets of X . We show that the subset Z of N consisting of Fréchet-differentiable norms whose dual norm is not strictly convex reduces any difference of analytic sets. It follows that Z is exactly a difference of analytic sets when N is equipped with the standard (...) Effros–Borel structure. Our main lemma elucidates the topological structure of the norm-attaining linear forms when the norm of X is locally uniformly rotund. (shrink)

Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parameterized problems that can be solved in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, (...) and it is shown that the class FPT of tractable parameterized problems has interesting and natural internal structure. (shrink)

A class K of structures is controlled if, for all cardinals λ, the relation of L ∞,λ-equivalence partitions K into a set of equivalence classes (as opposed to a proper class). We prove that the class of doubly transitive linear orders is controlled, while any pseudo-elementary class with the ω-independence property is not controlled.

The problem of computational complexity of semantics for some natural language constructions – considered in [M. Mostowski, D. Wojtyniak 2004] – motivates an interest in complexity of Ramsey quantifiers in finite models. In general a sentence with a Ramsey quantifier R of the following form Rx, yH(x, y) is interpreted as ∃A(A is big relatively to the universe ∧A2 ⊆ H). In the paper cited the problem of the complexity of the Hintikka sentence is reduced to the (...) problem of computational complexity of the Ramsey quantifier for which the phrase “A is big relatively to the universe” is interpreted as containing at least one representative of each equivalence class, for some given equvalence relation. In this work we consider quantifiers Rf, for which “A is big relatively to the universe” means “card(A) > f (n), where n is the size of the universe”. Following [Blass, Gurevich 1986] we call R mighty if Rx, yH(x, y) defines N P – complete class of finite models. Similarly we say that Rf is N P –hard if the corresponding class is N P –hard. We prove the following theorems. (shrink)

The expression of products encoded by the major histocompatibility complex (MHC) on tumor cells has recently been studied extensively. It has been found that many malignant tumor cells have their MHC antigens ‘switched‐off’ but that these antigens are re‐expressed following DNA‐mediated gene transfer, with increased tumor immunogenicity as a result and the consequence that these ‘transformed’ tumor cells are rejected in vivo.: This review will discuss approaches that have been taken to induce strong tumor‐specific immunity by the manipulation of MHC (...) expression on tumor cells. (shrink)

Using Marcuse's theory of the total mobilization of advanced technology society along the lines of what he calls “the performance principle,” I attempt to describe the complex composition of class oppression in the classroom. Students conceive of themselves as economic units, customers pursuing neutral interests in a morally neutral, socio‐economic system of capitalist competition. The classic, unreflective conception of the classroom responds to this by implicitly endorsing individualism and ideals of humanist citizenship. While racism and cultural diversity have come to (...) count as elements of liberal intelligence in most college curricula, attempts to theorize these aspects of social and individual identity and place them in a broader content of class appear radical and inconsistent with the humanistic notion that we all have control over who we are and what we achieve. But tags such as “radical” and “unrealistic” mark a society based on the performance principle. Marcuse allows us to recognize a single author behind elements of psychology, metaphysics, and capitalism. The fact that bell hooks hits upon a similar notion suggests that we might use Marcuse's theory of the truly liberatory potential of imagination to transform and reconceive our classrooms so that the insidious effects of class, racism, and individualistic apathy might be subverted. Specifically, I outline and place into this theoretical context three concrete pedagogical practices: (a) the use of the physical space of the classroom; (b) the performance of community through group readings and short full‐class ceremonies, and (c) the symbolic modeling represented by interdisciplinary approaches to teaching. All three of these practices engage students in ways that co‐curricularly subvert class (and, incidentally, race divisions) and allow students to imagine, and so engage in, political action for justice as they see it. (shrink)

The class approach to the problem of educating a comprehensively developed personality under the conditions of developed socialist society requires careful consideration of the full complexity of the social structure of contemporary socialist society and the resultant concrete connections and interrelations of classes, social strata, and groups. A class approach requires that social reality be evaluated from the standpoint of the objective tendencies it embodies and the progressive possibilities of historical development; it relies on real social strata capable (...) of and concerned with implementing these potentials. (shrink)

In computational complexity theory, decision problems are divided into complexity classes based on the amount of computational resources it takes for algorithms to solve them. In theoretical computer science, it is commonly accepted that only functions for solving problems in the complexity class P, solvable by a deterministic Turing machine in polynomial time, are considered to be tractable. In cognitive science and philosophy, this tractability result has been used to argue that only functions in P can (...) feasibly work as computational models of human cognitive capacities. One interesting area of computational complexity theory is descriptive complexity, which connects the expressive strength of systems of logic with the computational complexity classes. In descriptive complexity theory, it is established that only first-order (classical) systems are connected to P, or one of its subclasses. Consequently, second-order systems of logic are considered to be computationally intractable, and may therefore seem to be unfit to model human cognitive capacities. This would be problematic when we think of the role of logic as the foundations of mathematics. In order to express many important mathematical concepts and systematically prove theorems involving them, we need to have a system of logic stronger than classical first-order logic. But if such a system is considered to be intractable, it means that the logical foundation of mathematics can be prohibitively complex for human cognition. In this paper I will argue, however, that this problem is the result of an unjustified direct use of computational complexity classes in cognitive modelling. Placing my account in the recent literature on the topic, I argue that the problem can be solved by considering computational complexity for humanly relevant problem solving algorithms and input sizes. (shrink)

Recent years have seen an increasing interest in the study of continuous-time computational models. However, not so much has been done with respect to setting up a complexity theoretic framework for such models. The present paper intends to go a step into this direction. We consider problems over the real numbers which we try to relate to Lyapunov theory for dynamical systems: The global minimizers of particular energy functions are supposed to give solutions of the problem. The structure of (...) such energy functions leads to the introduction of problem classes U and NU; for the systems we are considering they parallel the classical complexity classes P and NP. We then introduce a notion of reducibility among problems and show existence of complete problems for NU and for PU, a polynomial hierarchy of continuous-time problems.For previous work on the computational capabilities of continuous-time systems see the surveys by Cris Moore [9] and by Pekka Orponen [10]. Our paper presents a step into the direction of creating a general framework for a complexity theory of continuous-time systems as outlined in [10]. It is closely related to work done by A. Ben-Hur, H. Siegelmann, and S. Fishman [12, 11]. (shrink)

We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite (...) path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem. (shrink)

Do political concerns belong in psychodynamic treatment? How do class and politics shape the unconscious? The effects of an increasingly polarized, insecure and threatening world mean that the ideologically enforced split between the political order and personal life is becoming difficult to sustain. This book explores the impact of the social and political domains at the individual level. The contributions included in this volume describe how issues of class and politics, and the intense emotions they engender, emerge in the clinical (...) setting and how psychotherapists can respectfully address them rather than deny their significance. They demonstrate how clinicians need to take into account the complex convergences between psychic and social reality in the clinical setting in order to help their patients understand the anxiety, fear, insecurity and anger caused by the complex relations of class and power. This examination of the psychodynamics of terror and aggression and the unconscious defences employed to deny reality offers powerful insights into the microscopic unconscious ways that ideology is enacted and lived. _Psychoanalysis, Class and Politics_ will be of interest to all mental health professionals interested in improving their understanding of the ideological factors that impede or facilitate critical and engaged citizenship. It has a valuable contribution to make to the psychoanalytic enterprise, as well as to related scholarly and professional disciplines. (shrink)

We design functional algebras that characterize various complexity classes of global functions. For this purpose, classical schemata from recursion theory are tailored for capturing complexity. In particular we present a functional analog of first-order logic and describe algebras of the functions computable in nondeterministic logarithmic space, deterministic and nondeterministic polynomial time, and for the functions computable by AC 1 -circuits.

A Martin-Löf random sequence is an infinite binary sequence with the property that every initial segment $\sigma$ has prefix-free Kolmogorov complexity $K$ at least $|\sigma| - c$, for some constant $c \in \omega$. Informally, initial segments of Martin-Löf randoms are highly complex in the sense that they are not compressible by more than a constant number of bits. However, all Martin-Löf randoms necessarily have contiguous substrings of arbitrarily low complexity. If we demand that all substrings of a sequence (...) be uniformly complex, then we arrive at the notion of shift-complex sequences. In this paper, we collect some of the existing results on these sequences and contribute two new ones. Rumyantsev showed that the measure of oracles that compute shift-complex sequences is zero. We strengthen this result by proving that the Martin-Löf random sequences that do not compute shift-complex sequences are exactly the incomplete ones, in other words, the ones that do not compute the halting problem. In order to do so, we make use of the characterization by Franklin and Ng of the class of incomplete Martin-Löf randoms via a notion of randomness called difference randomness. Turning to the power of shift-complex sequences as oracles, we show that there are shift-complex sequences that do not compute Martin-Löf random sequences. (shrink)

Many kinds of complex systems exhibit characteristic patterns of temporal correlations that emerge as the result of functional interactions within a structured network. One such complex system is the brain, composed of numerous neuronal units linked by synaptic connections. The activity of these neuronal units gives rise to dynamic states that are characterized by specific patterns of neuronal activation and co-activation. These patterns, called functional connectivity, are possible neural correlates of perceptual and cognitive processes. Which functional connectivity patterns arise depends (...) on the anatomical structure of the underlying network, which in turn is modified by a broad range of activity-dependent processes. Given this intricate relationship between structure and function, the question of how patterns of anatomical connectivity constrain or determine dynamical patterns is of considerable theoretical importance. The present study develops computational tools to analyze networks in terms of their structure and dynamics. We identify different classes of network, including networks that are characterized by high complexity. These highly complex networks have distinct structural characteristics such as clustered connectivity and short wiring length similar to those of large-scale networks of the cerebral cortex. (shrink)

Syntactic complexity effects have been investigated extensively with respect to comprehension . According to one prominent class of accounts , certain structures cause comprehension difficulty due to their scarcity in the language. But why are some structures less frequent than others? In two elicited-production experiments we investigated syntactic complexity effects in relative clauses and wh-questions varying in whether or not they contained non-local dependencies. In both experiments, we found reliable durational differences between subject-extracted structures and object-extracted structures : (...) Participants took longer to begin and produce object-extractions. Furthermore, participants were more likely to be disfluent in the object-extracted constructions. These results suggest that there is a cost associated with planning and uttering the more syntactically complex, object-extracted structures, and that this cost manifests in the form of longer durations and disfluencies. Although the precise nature of this cost remains to be determined, these effects provide one plausible explanation for the relative rarity of object-extractions: They are more costly to produce. (shrink)

Tarski [19] proved the important theorem that the class of representable relation algebras is equationally axiomatizable. One of the key steps in his proof is showing that the class of (isomorphs of) simple set relation algebras—that is, algebras of binary relations with a unit of the formU×Ufor some non-empty setU—is universal, i.e., is axiomatizable by a set of universal sentences. In the same paper Tarski observed that the class of (isomorphs of) relation algebras constructed from groups (so-calledgroup relation algebras) is (...) also universal.We shall abstract the essential ingredients of Tarski's method (in Corollary 2.4), and then combine them with some observations about atom structures, to establish (in Theorem 2.6) a rather general method for showing that certain classes of simple relation algebras—and, more generally, certain classes of simple algebras in a discriminator variety V—are universal, and consequently that the collections of (isomorphs of) subdirect products of algebras in such classes form subvarieties of V. As applications of the method we show that two well-known classes of simple relation algebras, those constructed from projective geometries (sometimes calledLyndon algebras) and those constructed from modular lattices with a zero (sometimes calledMaddux algebras), are universal. In the process we prove that these two classes consist precisely of all (isomorphs of) complex algebras over the respective geometries and modular lattices, provided that we choose the primitive notions of the latter structures in an appropriate fashion. We also derive Tarski's theorems and a related theorem of the author as easy corollaries of Theorem 2.6. (shrink)

Understanding the dynamics of complex ecosystems is a necessary step to maintain and control them. Yet, reverse-engineering ecological dynamics remains challenging largely due to the very broad class of dynamics that ecosystems may take. Here, this challenge is tackled through symbolic regression, a machine learning method that automatically reverse-engineers both the model structure and parameters from temporal data. How combining symbolic regression with a “dictionary” of possible ecological functional responses opens the door to correctly reverse-engineering ecosystem dynamics, even in the (...) case of poorly informative data, is shown. This strategy is validated using both synthetic and experimental data, and it is found that this strategy is promising for the systematic modeling of complex ecological systems. (shrink)

Complex demonstrative phrases, in English, are phrases such as ‘that woman in the department’ and ‘that car on the corner’. They are of particular interest to philosophers for two related reasons. The first involves the problem of intentionality. If there are phrases that are candidates for “latching directly onto the world,” they are such phrases, and their “simple” counterparts, as in the occurrences of ‘that’ in ‘that is nice’. As a result, philosophers interested in intentionality, from the sense-data theorists to (...) contemporary philosophers of mind, have devoted considerable attention to the question of how a demonstrative thought links to its object. The second reason involves issues in semantics and the philosophy of language. In the course of investigations into the model theory for modal logic in the 1950s and 1960s, philosophers recognized that the simplest way to treat terms was as modally rigid, namely as designating their actual designations relative to any possible world in which they existed, and nothing else in other worlds. It was soon recognized that this semantic property could be elegantly explained by the assumption that the semantics of singular terms reflects the role of singular terms in linking representations directly to the world. If the semantic contribution of a singular term to a thought is simply the object it denotes, and the thought is the object of modal evaluation, then the modal rigidity of the class of terms falls out as a consequence. Demonstrative phrases, both simple and complex, have always been taken to be among the paradigms for this picture of reference, which has come to be known as “the direct reference” model. (shrink)

We describe a decidable class of formulas in a first order timed logic that covers a good amount of properties of real-time distributed systems. Earlier we described a decidable class based on some finiteness properties, and sketched a decidable class in a weaker logic that captures periodicity properties, though without complete proof. The new feature of the decidable class presented here is to be able to treat parametric properties, in particular, properties that concern an arbitrary number of processes as compared (...) to the just mentioned class that could express only properties for a fixed, explicitly given number of processes. As before the properties may use non-trivial arithmetics. We also state another important feature of the class: if a verification formula is not true then our algorithm gives a quantifier-free description of all its counter-models of the complexity involved in the definition of the decidable class and that is quite representative. In conclusion we discuss theoretical and practical issues of the complexity and some open questions. (shrink)