In this paper we interpret a characterization of the Gödel speed-up phenomenon as providing support for the ‘Nagel-Newman thesis’ that human theorem recognizers differ from mechanical theorem recognizers in that the former do not seem to be limited by Gödel's incompleteness theorems whereas the latter do seem to be thus limited. However, we also maintain that (currently non-existent) programs which are open systems in that they continuously interact with, and are thus inseparable from, their environment, are not covered by the (...) above (or probably any other recursion-theoretic) argument. (shrink)

In this paper we interpret a characterization of the Gödel speed-up phenomenon as providing support for the ‘Nagel-Newman thesis’ that human theorem recognizers differ from mechanical theorem recognizers in that the former do not seem to be limited by Gödel's incompleteness theorems whereas the latter do seem to be thus limited.However, we also maintain that (currently non-existent) programs which are open systems in that they continuously interact with, and are thus inseparable from, their environment, are not covered by the above (...) (or probably any other recursion-theoretic) argument. (shrink)

Computational complexity theory is a subfield of computer science originating in computability theory and the study of algorithms for solving practical mathematical problems. Amongst its aims is classifying problems by their degree of difficulty — i.e., how hard they are to solve computationally. This paper highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones — e.g., about the notion of (...) feasibility in mathematics, the $\mathbf{P} \neq \mathbf{NP}$ problem and why it has proven hard to resolve, and the role of non-classical modes of computation and proof. (shrink)

Recently, several authors have explored the connections between NP-complete problems for finite objects and the complexity of their analogs for infinite objects. In this paper, we will categorize infinite versions of several problems arising from finite complexity theory in terms of their recursion theoretic complexity and proof theoretic strength. These infinite analogs can behave in a variety of unexpected ways.

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)

A central aim of cognitive science is to understand the fundamental mechanisms that enable humans to navigate and make sense of complex environments. In this letter, we argue that computational complexity theory, a foundational framework for evaluating computational resource requirements, holds significant potential in addressing this challenge. As humans possess limited cognitive resources for processing vast amounts of information, understanding how humans perform complex cognitive tasks requires comprehending the underlying factors that drive information processing demands. Computational complexity (...) theory provides a comprehensive theoretical framework to achieve this goal. By adopting this framework, we can gain new insights into how cognitive systems work and develop a more nuanced understanding of the relation between task complexity and human behavior. We provide empirical evidence supporting our argument and identify several open research questions and challenges in applying computational complexity theory to human decision‐making and cognitive science at large. (shrink)

This paper presents a number of objections to Jeffrey King's quantificational theory of complex demonstratives. Some of these objections have to do with modality, whereas others concern attitude ascriptions. Various possible replies are considered. The debate between quantificational theorists and direct reference theorists over complex demonstratives is compared with recent debates concerning definite descriptions.

I criticized Jeffrey King’s theory of complex demonstratives in “Problems for a Quantificational Theory of Complex Demonstratives.” King replied in “Complex Demonstratives as Quantifiers: Objections and Replies.” I here comment on some of King’s replies.

Around 1989, a striking letter written in March 1956 from Kurt Gödel to John von Neumann came to light. It poses some problems about the complexity of algorithms; in particular, it asks a question that can be seen as the first formulation of the P=?NP question. This paper discusses some of the background to this letter, including von Neumann's own ideas on complexity theory. Von Neumann had already raised explicit questions about the complexity of Tarski's (...) decision procedure for elementary algebra and geometry in a letter of 1949 to J. C. C. McKinsey. The paper concludes with a discussion of why theoretical computer science did not emerge as a separate discipline until the 1960s. (shrink)

The correct solution to complex problems, such as those involved in international relations, can generally be discovered ex post but not predicted ex ante. Economics and game theory attempt to model such complexity, but have difficulty taking into account psychological subtleties, the myriad factors that each agent considers when making a decision, and cultural differences. And understanding that one is dealing with a system—that is, with interacting factors instead of with insulated monads—may not make the questions any (...) more amenable to prediction, particularly because the more unique an event, the less likely it is to be foreseen. Jervis's analysis of complex systems may therefore be more of a contribution to the historical sciences than to predictive social science. (shrink)

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in (...) both classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees. (shrink)

We give a new characterization of the strict $$\forall {\Sigma^b_j}$$ sentences provable using $${\Sigma^b_k}$$ induction, for 1 ≤ j ≤ k. As a small application we show that, in a certain sense, Buss’s witnessing theorem for strict $${\Sigma^b_k}$$ formulas already holds over the relatively weak theory PV. We exhibit a combinatorial principle with the property that a lower bound for it in constant-depth Frege would imply that the narrow CNFs with short depth j Frege refutations form a strict hierarchy (...) with j, and hence that the relativized bounded arithmetic hierarchy can be separated by a family of $$\forall {\Sigma^b_1}$$ sentences. (shrink)

This book presents an up-to-date, unified treatment of research in bounded arithmetic and complexity of propositional logic, with emphasis on independence proofs and lower bound proofs. The author discusses the deep connections between logic and complexity theory and lists a number of intriguing open problems. An introduction to the basics of logic and complexity theory is followed by discussion of important results in propositional proof systems and systems of bounded arithmetic. More advanced topics are (...) then treated, including polynomial simulations and conservativity results, various witnessing theorems, the translation of bounded formulas (and their proofs) into propositional ones, the method of random partial restrictions and its applications, direct independence proofs, complete systems of partial relations, lower bounds to the size of constant-depth propositional proofs, the method of Boolean valuations, the issue of hard tautologies and optimal proof systems, combinatorics and complexity theory within bounded arithmetic, and relations to complexity issues of predicate calculus. Students and researchers in mathematical logic and complexity theory will find this comprehensive treatment an excellent guide to this expanding interdisciplinary area. (shrink)

Complexity theories are on the way to establish a new worldview—processes instead of objects, history and uniqueness of everything instead of repetition and lawlikeness are the elements. These theories from deterministic chaos via the dissipative structures, the theory of catastrophes, self organization and synergetics are mathematical models, connected with a new understanding of science. They are characterized by new fundamental commitments of sciences. But at the same time, they are characterized by epistemic boundaries.

This research calls for attention to complexity theory and the integration of complexity methodologies in policy research. A complexity approach in research practice requires a systems worldview and recognition of non-linearity, networks, self-organization, emergence, and feedback in policy. Simply, if a phenomenon is complex and can be explored from varied contexts and scales, the conceptual frame, and the methodical approach should be able to address the complexity. Complexity science has the capacity to account for (...) complexity in varied contexts, on varied scales, and with an interrelated and interdependent environment. Further, if policy systems are at times simple, complicated, complex, and chaotic, then complexity mythologies combined with traditional qualitative and quantitative methods can bring to light the workings of the elusive black box. Complexity allows for triangulation of both linear and non-linear methodologies integrating qualitative, quantitative, network analysis, and agent-based models, as well as other methodologies. Complexity science is not the panacea to solve all policy problems with perfection. But if you do not acknowledge the complexity you will be missing out on the opportunity to shape patterns of sustainability, to effectively manage complex policy problems to someday solve them. (shrink)

Resumen Este texto formula una teoría de los problemas complejos, que trata de distinguir cuándo y cómo un problema puede ser dicho como complejo y cuándo no. Un mundo diferente de suma cero, altamente entreverado, con múltiples sensibilidades y con crisis sistémicas y sistemáticas demanda una teoría de problemas complejos, inexistente a la fecha. Negativamente, las comprensiones o aproximaciones analíticas son insuficientes. Es precisa una estructura sintética sobre los problemas. Para ello, tres ejes emergen como referencias: la teoría matemática de (...) nudos, la teoría de la complejidad computacional y los problemas retorcidos. Este texto elabora una síntesis de estos tres ejes y propone una teoría para problemas entrelazados, dinámicos, difíciles, con fuertes implicaciones en varios planos y contextos entre sí. En una cuarta sección se trata de apreciar cómo la teoría de los problemas complejos contribuye a la epistemología de las ciencias sociales. Abstract This paper brings forth a theory of complex problems, distinguishing when and why a problem can be said to be complex, and when and why not. A world of non-zero sum, highly intertwined, with multiple sensitivities, with systemic and systematic crises requires a theory of complex systems, which does not exist today. Negatively said, analytical understandings and approaches are insufficient. It is needed, we argue, a synthetic structure regarding problems. Henceforth three axes emerge as referents: mathematical knots theory, theory of computational complexity, and the wicked problems. This paper consists of a synthesis of the three axes, and develops a theory for problems highly intertwined, dynamic, difficult, and with strong implications in various levels and contexts. A fourth section is devoted to the study of how the epistemology of the social sciences can benefit from the theory of complex systems. (shrink)

Relations between discrete and continuous complexity models are considered. The present paper is devoted to combine both models. In particular we analyze the 3-Satisfiability problem. The existence of fast decision procedures for this problem over the reals is examined based on certain conditions on the discrete setting. Moreover we study the behaviour of exponential time computations over the reals depending on the real complexity of 3-Satisfiability. This will be done using tools from complexity theory over the (...) integers. (shrink)

Current organizational communication theorists and practitioners seek to remedy organizational ills by advancing democracy within the workplace. Specifically, organizational democracy has been introduced with a variety of goals in mind: improving representation, increasing job satisfaction, improving productivity, and reducing costs. Although democracy emerges in myriad forms, theorists are still uncertain as to how to involve employees in the process and produce observable results. In this article, recent developments in complexity theory are invoked to both illuminate and resolve (...) class='Hi'>problems on the perspective of workplace democracy. The article closes by showing how complexity theory concepts can be used to encourage democratic practices in organizations. Ultimately, complexity theory is used to shed light on the processes surrounding the considerable problem solving and experimentation required to implement democratic practices. (shrink)

In this paper we study generic complexity of undecidable problems. It turns out that some classical undecidable problems are, in fact, strongly undecidable, i.e., they are undecidable on every strongly generic subset of inputs. For instance, the classical Halting Problem is strongly undecidable. Moreover, we prove and analog of the Rice theorem for strongly undecidable problems, which provides plenty of examples of strongly undecidable problems. Then we show that there are natural super-undecidable problems. i.e., (...) problem which are undecidable on every generic (not only strongly generic) subset of inputs. In particular, there are finitely presented semigroups with super-undecidable word problem. To construct strongly- and super-undecidable problems we introducea method of generic amplification (an analog of the amplification in complexity theory). Finally, we construct absolutely undecidable problems, which stay undecidable on every non-negligible set of inputs. Their construction rests on generic immune sets. (shrink)

Rice's Theorem says that every nontrivia semantic property of programs is undecidable. In this spirit we show the following: Every nontrivia absolute counting property of circuits is UP-hard with respect to polynomial-time Turing reductions. For generators [31] we show a perfect analogue of Rice's Theorem.

Semiclassical theory based upon complexified classical mechanics is developed for periodically time-dependent scattering systems, which are minimal models of multi-dimensional systems. Semiclassical expression of the wave-matrix is derived, which is represented as the sum of the contributions from classical trajectories, where all the dynamical variables as well as the time are extended to the complex-domain. The semiclassical expression is examined by a periodically perturbed 1D barrier system and an excellent agreement with the fully quantum result is confirmed. In a (...) stronger perturbation regime, the tunneling component of the wave-matrix exhibits a remarkable interference fringes, which is clarified by the semiclassical theory as an interference among multiple complex tunneling trajectories. It turns out that such a peculiar behavior is the manifestation of an intrinsic multi-dimensional effect closely related to a singular movement of singularities possessed by the complex classical trajectories. (shrink)

I here discuss two problems facing Russellian act-type theories of propositions, and argue that Fregean act-type theories are better equipped to deal with them. The first relates to complex singular terms like '2+2', which turn out not to pose any special problem for Fregeans at all, whereas Soames' theory currently has no satisfactory way of dealing with them (particularly, with such "mixed" propositions as the proposition that 2+2 is greater than 3). Admittedly, one possibility stands out as the (...) most promising one, but it requires that the Russellian treat complex properties as constituents of propositions. This leads to the second major problem for Russellians: that of proliferating propositions. I show how the most direct solution to this problem, that of rejecting complex predicative propositional constituents is available to Fregeans but very implausible for Russellians, since this virtually means rejecting complex properties. (shrink)

The hard problem of consciousness arises in most incarnations of present day physicalism. Why should certain physical processes necessarily be accompanied by experience? One possible response is that physicalism itself should be modified in order to accommodate experience: But, modified how? In the present work, we investigate whether an ontology derived from quantum field theory can help resolve the hard problem. We begin with the assumption that experience cannot exist without being accompanied by a subject of experience (SoE). While (...) people well versed in Indian philosophy will not find that statement problematic, it is still controversial in the analytic tradition. Luckily for us, Strawson has elaborately defended the notion of a thin subject—an SoE which exhibits a phenomenal unity with different types of content (sensations, thoughts etc.) occurring during its temporal existence. Next, following Stoljar, we invoke our ignorance of the true physical as the reason for the explanatory gap between present day physical processes (events, properties) and experience. We are therefore permitted to conceive of thin subjects as related to the physical via a new, yet to be elaborated relation. While this is difficult to conceive under most varieties of classical physics, we argue that this may not be the case under certain quantum field theory ontologies. We suggest that the relation binding an SoE to the physical is akin to the relation between a particle and (quantum) field. In quantum field theory, a particle is conceived as a coherent excitation of a field. Under the right set of circumstances, a particle coalesces out of a field and dissipates. We suggest that an SoE can be conceived as akin to a particle—a SelfOn—which coalesces out of physical fields, persists for a brief period of time and then dissipates in a manner similar to the phenomenology of a thin subject. Experiences are physical properties of selfons with the constraint (specified by a similarity metric) that selfons belonging to the same natural kind will have similar experiences. While it is odd at first glance to conceive of subjects of experience as akin to particles, the spatial and temporal unity exhibited by particles as opposed to fields and the expectation that selfons are new kinds of particles, paves the way for cementing this notion. Next, we detail the various no-go theorems in most versions of quantum field theory and discuss their impact on the existence of selfons. Finally, we argue that the time is ripe for a rejuvenated Indian philosophy to begin tackling the three-way relationship between SoEs (which may become equivalent to jivas in certain Indian frameworks), phenomenal content and the physical world. With analytic philosophy still struggling to come to terms with the complex worlds of quantum field theory and with the relative inexperience of the western world in arguing the jiva-world relation, there is a clear and present opportunity for Indian philosophy to make a worldcentric contribution to the hard problem of experience. (shrink)

Introduction -- Elucidating complexity theories -- Complexity in the natural sciences -- Complexity in social theory -- Towards transdisciplinarity -- Complexity in philosophy: complexification and the limits to knowledge -- Complexity in ethics -- Earth in the anthropocene -- Complexity and climate change -- American dreams, ecological nightmares and new visions -- Complexity and sustainability: wicked problems, gordian knots and synergistic solutions -- Conclusion.

In this paper I suggest that several problems in the study of emotion depend on a lack of adequate analytical tools, in particular on the tendency of viewing the organism as a modular and hierarchical system whose activity is mainly constituted by strictly sequential causal events. I argue that theories and models based on this view are inadequate to account for the complex reciprocal influences of the many ingredients that constitute emotions. Cognitive processes, feelings and bodily states are so (...) subtly intertwined that it is not possible to determine which one "comes first" in a causal chain. The dynamical systems approach in cognitive science, I suggest, provides a more appropriate framework for the study of emotion. In particular, the notion of circular causation and collective action help depict the organism as a self-organising system in which emotion emerges as a function of its global activity. Among others, this dynamical perspective allows revising the popular notion of appraisal in a way that can dissolve some of the questions that have taunted emotion theorists thus far. (shrink)

We propose two alternatives to Xu’s axiomatization of Chellas’s STIT. The first one simplifies its presentation, and also provides an alternative axiomatization of the deliberative STIT. The second one starts from the idea that the historic necessity operator can be defined as an abbreviation of operators of agency, and can thus be eliminated from the logic of Chellas’s STIT. The second axiomatization also allows us to establish that the problem of deciding the satisfiability of a STIT formula without temporal operators (...) is NP-complete in the single-agent case, and is NEXPTIME-complete in the multiagent case, both for the deliberative and Chellas’s STIT. (shrink)

Systems change requires complex interventions. Cross-sector partnerships face the daunting task of addressing complex societal problems by aligning different backgrounds, values, ideas and resources. A major challenge for CSPs is how to link the type of partnership to the intervention needed to drive change. Intervention strategies are thereby increasingly based on Theories of Change. Applying ToCs is often a donor requirement, but it also reflects the ambition of a partnership to enhance its transformative potential. The current use of ToCs (...) in partnering efforts varies greatly. There is a tendency for a linear and relatively simple use of ToCs that does limited justice to the complexity of the problems partnerships aim to address. Since partnership dynamics are already complex and challenging themselves, confusion and disagreement over the appropriate application of ToCs is likely to hamper rather than enhance the transformative potential of partnerships. We develop a complexity alignment framework and a diagnostic tool that enables partnerships to better appreciate the complexity of the context in which they operate, allowing them to adjust their learning strategy. This paper applies recent insights into how to deal with complexity from both the evaluation and theory of change fields to studies investigating the transformative capacity of partnerships. This can serve as a check to define the challenges of partnering projects and can help delineate the societal sources and layers of complexity that cross-sector partnerships deal with such as failure, insufficient responsibility taking and collective action problems at four phases of partnering. (shrink)

This article explores the affinities and parallels between Foucault's Nietzschean view of history and models of complexity developed in the physical sciences in the twentieth century. It claims that Foucault's rejection of structuralism and Marxism can be explained as a consequence of his own approach which posits a radical ontology whereby the conception of the totality or whole is reconfigured as an always open, relatively borderless system of infinite interconnections, possibilities and developments. His rejection of Hegelianism, as well as (...) of other enlightenment philosophies, can be understood at one level as a direct response to his rejection of the mechanical atomist, and organicist epistemological world views, based upon a Newtonian conception of a closed universe operating upon the basis of a small number of invariable and universal laws, by which all could be predicted and explained. The idea of a fully determined, closed universe is replaced; and in a way parallel to complexity theories, Foucault's own approach emphasises notions such as self‐organisation and dissipative structures; time as an irreversible, existential dimension; a world of finite resources but with infinite possibilities for articulation, or re‐investment; and characterised by the principles of openness, indeterminism, unpredictability, and uncertainty. The implications of Foucault's type of approach are then explored in relation to identity, creativity, and the uniqueness of the person. The article suggests that within a complexity theory approach many of the old conundrums concerning determinism and creativity, social constructionism and uniqueness, can be overcome. (shrink)

Epicurus emphatically asserts the veracity of perception, including visual perception, yet most of the literature on Epicurus’ atomistic theory of vision pays scant attention to what Epicurus believed transpires outside the body that leads to it. The treatments by DeWitt, Everson, Hicks, and Rist are all very brief; Glidden focuses primarily on the processes occurring inside the perceiver; and while the discussions by Asmis and Bailey are more detailed, they hardly more than note in passing that the process is (...) problematic.1 In this paper I will critically examine Epicurus’ theory of vision, in particular his theory of the events occurring between perceived objects and the eye. I will argue that while certain common objections to Epicurus’ theory may be answerable, it nevertheless suffers from serious problems. These problems, in turn, occur on two levels. On the mechanical level, it demands that dissimilar atomic complexes behave in strikingly similar ways. And on the theoretical level, there is tension created by the need for the intermediary between objects and the observer to be both like objects and unlike them. (shrink)

Systems change requires complex interventions. Cross-sector partnerships face the daunting task of addressing complex societal problems by aligning different backgrounds, values, ideas and resources. A major challenge for CSPs is how to link the type of partnership to the intervention needed to drive change. Intervention strategies are thereby increasingly based on Theories of Change. Applying ToCs is often a donor requirement, but it also reflects the ambition of a partnership to enhance its transformative potential. The current use of ToCs (...) in partnering efforts varies greatly. There is a tendency for a linear and relatively simple use of ToCs that does limited justice to the complexity of the problems partnerships aim to address. Since partnership dynamics are already complex and challenging themselves, confusion and disagreement over the appropriate application of ToCs is likely to hamper rather than enhance the transformative potential of partnerships. We develop a complexity alignment framework and a diagnostic tool that enables partnerships to better appreciate the complexity of the context in which they operate, allowing them to adjust their learning strategy. This paper applies recent insights into how to deal with complexity from both the evaluation and theory of change fields to studies investigating the transformative capacity of partnerships. This can serve as a check to define the challenges of partnering projects and can help delineate the societal sources and layers of complexity that cross-sector partnerships deal with such as failure, insufficient responsibility taking and collective action problems at four phases of partnering. (shrink)

Instead of postulated fixed structures and abstract principles of usual positivistic science, the unreduced diversity of living world reality is consistently derived as dynamically emerging results of unreduced interaction process development, starting from its simplest configuration of two coupled homogeneous protofields. The dynamically multivalued, or complex and intrinsically chaotic, nature of these real interaction results extends dramatically the artificially reduced, dynamically single-valued projection of standard theory and solves its stagnating old and accumulating new problems, “mysteries” and “paradoxes” within (...) the unified and causally complete picture of intrinsically evolving, dynamically complex reality. The permanently unfolding complexity progress thus revealed is fundamentally unlimited and does not need to stop at the directly observed diversity of usual matter complexity. The exciting, but rigorously substantiated and objectively inevitable prospects of further civilisation complexity development towards its superior levels of genuine sustainability and global Noosphere are outlined, with practically important conclusions for today’s critical problem solution. (shrink)

This work presents a systematic study of decision problems for equational theories of algebras of binary relations (relation algebras). For example, an easily applicable but deep method, based on von Neumann's coordinatization theorem, is developed for establishing undecidability results. The method is used to solve several outstanding problems posed by Tarski. In addition, the complexity of intervals of equational theories of relation algebras with respect to questions of decidability is investigated. Using ideas that go back to Jonsson (...) and Lyndon, the authors show that such intervals can have the same complexity as the lattice of subsets of the set of the natural numbers. Finally, some new and quite interesting examples of decidable equational theories are given. The methods developed in the monograph show promise of broad applicability. They provide researchers in algebra and logic with a new arsenal of techniques for resolving decision questions in various domains of algebraic logic. (shrink)

Systems change requires complex interventions. Cross-sector partnerships (CSPs) face the daunting task of addressing complex societal problems by aligning different backgrounds, values, ideas and resources. A major challenge for CSPs is how to link the type of partnership to the intervention needed to drive change. Intervention strategies are thereby increasingly based on Theories of Change (ToCs). Applying ToCs is often a donor requirement, but it also reflects the ambition of a partnership to enhance its transformative potential. The current use (...) of ToCs in partnering efforts varies greatly. There is a tendency for a linear and relatively simple use of ToCs that does limited justice to the complexity of the problems partnerships aim to address. Since partnership dynamics are already complex and challenging themselves, confusion and disagreement over the appropriate application of ToCs is likely to hamper rather than enhance the transformative potential of partnerships. We develop a complexity alignment framework and a diagnostic tool that enables partnerships to better appreciate the complexity of the context in which they operate, allowing them to adjust their learning strategy. This paper applies recent insights into how to deal with complexity from both the evaluation and theory of change fields to studies investigating the transformative capacity of partnerships. This can (1) serve as a check to define the challenges of partnering projects and (2) can help delineate the societal sources and layers of complexity that cross-sector partnerships deal with such as failure, insufficient responsibility taking and collective action problems at four phases of partnering. (shrink)

We study the computational complexity of finding a line that bisects simultaneously two sets in the two-dimensional plane, called the pancake problem, using the oracle Turing machine model of Ko. We also study the basic problem of bisecting a set at a given direction. Our main results are: (1) The complexity of bisecting a nice (thick) polynomial-time approximable set at a given direction can be characterized by the counting class #P. (2) The complexity of bisecting simultaneously two (...) linearly separable nice (thick) polynomial-time approximable sets can be characterized by the counting class #P. (3) For either of these two problems, without the thickness condition and the linear separability condition (for the two-set case), it is arbitrarily hard to compute the bisector, even if it is unique. (shrink)

Research in the fields of complex problem solving (CPS) and dynamic decision making using microworlds has been mainly conducted in Western industrialized countries. This study analyzes the CPS process by investigating thinking‐aloud protocols in five countries. Participants were 511 students from Brazil, Germany, India, the Philippines, and the United States who worked on two microworlds. On the basis of cultural‐psychological theories, specific cross‐national differences in CPS strategies were hypothesized. Following theories of situatedness of cognition, hypotheses about the specific frequency of (...) problem‐solving strategies in the two microworlds were developed. Results of the verbal protocols showed (a) modification of the theoretical CPS model, (b) task dependence of CPS strategies, and (c) cross‐national differences in CPS strategies. Participants’ CPS processes were particularly influenced by country‐specific problem‐solving strategies. (shrink)

Should we act only for the sake of what we might bring about (causal decision theory); or is it enough for a decent motive that our action is highly correlated with something desirable (evidential decision theory)? The conflict between these points of view is embodied in Newcomb's problem. It is argued here that intuitive evidence from familiar decision contexts does not enable us to settle the issue, since the two theories dictate the same results in normal circumstances. Nevertheless, (...) there are several reasons to reject the causal approach: (1) its relative complexity; (2) its commitment to the existence of situations in which every possible act would be irrational; (3) its incorporation of an arbitrary time bias; and (4) its implicit distinction between what ought to be done and what ought to be hoped for. (shrink)

In recent years, many philosophers of science have attempted to articulate a theory of non-epistemic emergence that is compatible with mechanistic explanation and incompatible with reductionism. The 2005 account of Fred C. Boogerd et al. has been particularly influential. They argued that a systemic property was emergent if it could not be predicted from the behaviour of less complex systems. Here, I argue that Boogerd et al.'s attempt to ground emergence in complexity guarantees that we will see emergence, (...) but at the cost of rendering it either trivial or epistemic. There are three basic problems. First, neither the measures of complexity explicitly mentioned by Boogerd et al. nor the most popular measures in the literature can do the practical and theoretical work that they assign to complexity. Second, I argue that while the success of their view depends on restricting the base of information available to the reductionist, this cannot be done in a way that is metaphysically neutral with respect to emer.. (shrink)

The class \ of t rue p airing a lgebras is defined to be the class of relation algebras expanded with concrete set theoretical projection functions. The main results of the present paper is that neither the equational theory of \ nor the first order theory of \ are decidable. Moreover, we show that the set of all equations valid in \ is exactly on the \ level. We consider the class \ of the relation algebra reducts of (...) \ ’s, as well. We prove that the equational theory of \ is much simpler, namely, it is recursively enumerable. We also give motivation for our results and some connections to related work. (shrink)

There are five basic types of ontology of law identified in relation with the singling out simpIe ontological objects in a strong or weak sense, dualist ontological objects, and complex ontalogical objects in a strong or weak sense. The conceptians of law far mulated in the theories/philosophies/ of law are ascribed to these five types.

An extended analysis compared to observations shows that modern “globalised” world civilisation has passed through the invisible “complexity threshold”, after which usual “spontaneous”, empirically driven kind of development (“invisible hand” etc.) cannot continue any more without major destructive tendencies. A much deeper, non-simplified understanding of real interaction complexity is necessary in order to cope with such globalised world development problems. Here we introduce the universal definition, fundamental origin, and dynamic equations for a major related quantity of (systemic) (...) risk characterising real complex system development tendencies at any level of dynamics. Practically important conclusions are derived, opening further detailed applications in economy, finance and development practice. (shrink)

Open peer commentary on the article “Observing Environments” by Hugo F. Alrøe & Egon Noe. Upshot: We discuss the environmental terminology of Jakob von Uexküll in the context of Alrøe Egon Noe’s reflections, and to examine more deeply the multi-perspectivity that arises from a combination of von Uexküll’s and Luhmann’s systems theories. The complexity yielded by an unpacking of the term “environment” sheds light on the difficulties in finding common understandings for solving wicked problems.

A novel conceptual framework is introduced for the Complexity Levels Theory in a Categorical Ontology of Space and Time. This conceptual and formal construction is intended for ontological studies of Emergent Biosystems, Super-complex Dynamics, Evolution and Human Consciousness. A claim is defended concerning the universal representation of an item’s essence in categorical terms. As an essential example, relational structures of living organisms are well represented by applying the important categorical concept of natural transformations to biomolecular reactions and relational (...) structures that emerge from the latter in living systems. Thus, several relational theories of living systems can be represented by natural transformations of organismic, relational structures. The ascent of man and other living organisms through adaptation, is viewed in novel categorical terms, such as variable biogroupoid representations of evolving species. Such precise but flexible evolutionary concepts will allow the further development of the unifying theme of local-to-global approaches to highly complex systems in order to represent novel patterns of relations that emerge in super- and ultra-complex systems in terms of compositions of local procedures. Solutions to such local-to-global problems in highly complex systems with ‘broken symmetry’ might be possible to be reached with the help of higher homotopy theorems in algebraic topology such as the generalized van Kampen theorems (HHvKT). Categories of many-valued, Łukasiewicz-Moisil (LM) logic algebras provide useful concepts for representing the intrinsic dynamic ‘asymmetry’ of genetic networks in organismic development and evolution, as well as to derive novel results for (non-commutative) Quantum Logics. Furthermore, as recently pointed out by Baianu and Poli (Theory and applications of ontology, vol 1. Springer, Berlin, in press), LM-logic algebras may also provide the appropriate framework for future developments of the ontological theory of levels with its complex/entangled/intertwined ramifications in psychology, sociology and ecology. As shown in the preceding two papers in this issue, a paradigm shift towards non-commutative, or non-Abelian, theories of highly complex dynamics—which is presently unfolding in physics, mathematics, life and cognitive sciences—may be implemented through realizations of higher dimensional algebras in neurosciences and psychology, as well as in human genomics, bioinformatics and interactomics. (shrink)

The structural approach to alternatives :669–690, 2007; Fox and Katzir in Nat Lang Semant 19:87–107, 2011; Katzir in Semantics, pragmatics and the case of scalar implicatures, Palgrave Macmillan, London, pp 40–71, 2014) is the most developed attempt in the literature at solving the symmetry problem of scalar implicatures. Problematic data with indirect and particularised scalar implicatures have however been raised :249–270, 2015). To address these problems, Trinh and Haida proposed to augment the theory with the Atomicity Constraint. Here (...) we show that this constraint falls short of explaining minimal variants of the original problems, and moreover that it runs into trouble with the inferences of sentences involving gradable adjectives like full and empty. We furthermore discuss how the structural approach suffers at times from the problem of ‘too many lexical alternatives’ pointed out by Swanson :31–36, 2010), and at other times from the opposite problem of ‘too few lexical alternatives’. These three problems epitomise the challenge of constructing just enough alternatives under the structural approach to solve the symmetry problem in full generality. Finally, we also sketch another recent attempt at solving the symmetry problem, Bergen et al., 2016), which is based on relative informativity and complexity. We argue that Bergen et al. do not provide a general solution to the symmetry problem either, by pointing to some of the open problematic cases that remain for this approach as well. We conclude that while important progress has been made in the theory of alternatives for scalar implicatures in the last few years, a full solution to the symmetry problem has not yet been attained. (shrink)

Psychological theory and research in ethical decision making and ethical professional practice are presently hampered by a failure to take appropriate account of an extensive background in moral philosophy. As a result, attempts to develop models of ethical decision making are left vulnerable to a number of criticisms: that they neglect the problems of meta-ethics and the variety of meta-ethical perspectives; that they fail clearly and consistently to differentiate between descriptive and prescriptive accounts; that they leave unexplicated the (...) theoretical assumptions derived from the underlying moral theories; and that they fail to accommodate the complexity and comprehensiveness of the processes involved in the making and implementing of ethical decisions. Many of these problems also have implications for the methodological domain. This paper offers an analysis of the difficulties, and makes a number of recommendations for future theory, research and practical applications, including: the need for training in moral philosophy; clarification of the status of Professional Codes in decisional models; the development of theoretically comprehensive prescriptive models; and the testing of these models in ways that do justice to their dimensional scope and theoretical complexity. (shrink)

The structural approach to alternatives :669–690, 2007; Fox and Katzir in Nat Lang Semant 19:87–107, 2011; Katzir in Semantics, pragmatics and the case of scalar implicatures, Palgrave Macmillan, London, pp 40–71, 2014) is the most developed attempt in the literature at solving the symmetry problem of scalar implicatures. Problematic data with indirect and particularised scalar implicatures have however been raised :249–270, 2015). To address these problems, Trinh and Haida proposed to augment the theory with the Atomicity Constraint. Here (...) we show that this constraint falls short of explaining minimal variants of the original problems, and moreover that it runs into trouble with the inferences of sentences involving gradable adjectives like full and empty. We furthermore discuss how the structural approach suffers at times from the problem of ‘too many lexical alternatives’ pointed out by Swanson :31–36, 2010), and at other times from the opposite problem of ‘too few lexical alternatives’. These three problems epitomise the challenge of constructing just enough alternatives under the structural approach to solve the symmetry problem in full generality. Finally, we also sketch another recent attempt at solving the symmetry problem, Bergen et al., 2016), which is based on relative informativity and complexity. We argue that Bergen et al. do not provide a general solution to the symmetry problem either, by pointing to some of the open problematic cases that remain for this approach as well. We conclude that while important progress has been made in the theory of alternatives for scalar implicatures in the last few years, a full solution to the symmetry problem has not yet been attained. (shrink)

Translation abstractSummary: Control versus Complexity: Approaches to the Carbon Dioxide Problem at IIASA. In the 1970s and 1980s the International Institute for Applied Systems Analysis (IIASA) hosted several research projects, workshops and conferences in order to discuss the implications of rising carbon dioxide concentrations in the Earth's atmosphere. A number of distinguished scholars, some of whom later became prominent protagonists within the United Nations’ Intergovernmental Panel on Climate Change (IPCC) and sustainability communities more generally, participated in these debates. Since (...) those at IIASA did not engage in obviously related fields such as geophysics or climatology, there is a need to explain how, and via which contexts the issue entered the institute's agenda. This article examines this historical context and contrasts two competing paradigms that emerged at IIASA in order to assess and respond to the carbon dioxide question: The first approach was related to the organisation's research projects on the future of energy systems, which drew on physics, engineering, economics and applied system dynamical modeling; the second approach drew earlier research into ecological management and complex dynamical systems theory, and argued for the use of multiple methods to assess the carbon dioxide question. The first approach invoked ideas of techno‐economical control mechanisms, the second resulted in a more embedded framing of climate change as one of a larger complex of issues relating to sustainable development. Based on resources from IIASA's research repositories and institutional archive, this study retraces these competing discourse framings and outlines the specific research and modeling strategies, policies, and cultural and technological imaginaries related to them. (shrink)