For regular sets in Euclidean space, previous work has identified twelve ‘basic’ computability notions to which many previous notions considered in literature were shown to be equivalent. With respect to those basic notions we now investigate on the computability of natural operations on regular sets: union, intersection, complement, convex hull, image, and pre-image under suitable classes of functions. It turns out that only few of these notions are suitable in the sense of rendering all those operations uniformly computable.

We study operator equations within the Turing machine based framework for computability in analysis. Is there an algorithm that maps pairs to solutions of Tx = u ? Here we consider the case when T is a bounded linear mapping between Hilbert spaces. We are in particular interested in computing the generalized inverse T†u, which is the standard concept of solution in the theory of inverse problems. Typically, T† is discontinuous and hence no computable mapping. However, we will use (...) effective versions of theorems from the theory of regularization to show that the mapping ↦ T†u is computable. We then go on to study the computability of average-case solutions with respect to Gaussian measures which have been considered in information based complexity. Here, T† is considered as an element of an L2-space. We define suitable representations for such spaces and use the results from the first part of the paper to show that ↦ T† is computable. (shrink)

The functional capabilities that consciousness seems to provide to biological systems can supply valuable principles in the design of more autonomous and robust technical systems. These functional concepts keep a notable similarity to those underlying the notion of operating system in software engineering, which allows us to specialize the computer metaphor for the mind into that of the operating system metaphor for consciousness. In this article, departing from these ideas and a model-based theoretical framework for cognition, we present an architectural (...) proposal for machine consciousness, called the Operative Mind. According to it, machine consciousness could be implemented as a set of services, in an operative system fashion, based on modeling of the own control architecture, that supervise the adequacy of the system architectural structure to the current objectives, triggering and managing adaptativity mechanisms. (shrink)

This paper analyses the impact of representation and search operators on Computational Complexity. A model of computation is introduced based on a directed graph, and representation and search are defined to be the vertices and edges of this graph respectively. Changing either the representation or the search algorithm leads to different possible complexity classes. The final section explores the role of representation in reducing time complexity in Artificial Intelligence.

For any class of operators which transform unary total functions in the set of natural numbers into functions of the same kind, we define what it means for a real function to be uniformly computable or conditionally computable with respect to this class. These two computability notions are natural generalizations of certain notions introduced in a previous paper co-authored by Andreas Weiermann and in another previous paper by the same authors, respectively. Under certain weak assumptions about the (...) class in question, we show that conditional computability is preserved by substitution, that all conditionally computable real functions are locally uniformly computable, and that the ones with compact domains are uniformly computable. The introduced notions have some similarity with the uniform computability and its non-uniform extension considered by Katrin Tent and Martin Ziegler, however, there are also essential differences between the conditional computability and the non-uniform computability in question. (shrink)

We introduce the computable FS-jump, an analog of the classical Friedman–Stanley jump in the context of equivalence relations on the natural numbers. We prove that the computable FS-jump is proper with respect to computable reducibility. We then study the effect of the computable FS-jump on computably enumerable equivalence relations (ceers).

In this paper we investigate computable isomorphisms of Boolean algebras with operators (BAOs). We prove that there are examples of polymodal Boolean algebras with finitely many computable isomorphism types. We provide an example of a polymodal BAO such that it has exactly one computable isomorphism type but whose expansions by a constant have more than one computable isomorphism type. We also prove a general result showing that BAOs are complete with respect to the degree spectra (...) of structures, computable dimensions, expansions by constants, and the degree spectra of relations. (shrink)

Combinatorial operations on sets are almost never well defined on Turing degrees, a fact so obvious that counterexamples are worth exhibiting. The case we focus on is the symmetric-difference operator; there are pairs of degrees for which the symmetric-difference operation is well defined. Some examples can be extracted from the literature, e.g. from the existence of nonzero degrees with strong minimal covers. We focus on the case of incomparable r.e. degrees for which the symmetric-difference operation is well defined.

The connected and acyclic components contained in a network are identified by the computation of its complexity, where complexity of a network refers to the total number of spanning trees present within. The article in hand deals with the enumeration of the complexity of various networks’ operations such as sum, product, difference K 2, n ⊖ K 2, and the conjunction of S n with K 2. All our computations have been concluded by implementation of the methods of linear algebra (...) and matrix theory. Our derivations will also be highlighted with the assistance of 3D plots at the end of this article. (shrink)

Computer models and simulations have become, since the 1960s, an essential instrument for scientific inquiry and political decision making in several fields, from climate to life and social sciences. Philosophical reflection has mainly focused on the ontological status of the computational modeling, on its epistemological validity and on the research practices it entails. But in computational sciences, the work on models and simulations are only two steps of a longer and richer process where operations on data are as important as, (...) and even more time and energy-consuming than modeling itself. Drawing on two study cases—computational embryology and computational epidemiology—this article contributes to filling the gap by focusing on the operations of producing and re-using data in computational sciences. The different phases of the scientific and artisanal work of modelers include data collection, aggregation, homogenization, assemblage, analysis and visualization. The article deconstructs the ideas that data are self-evident informational aggregates and that data-driven approaches are exempted from theoretical work. More importantly, the paper stresses the fact that data are constructed and theory laden not only in their fabrication, but also in their reusing. (shrink)

We develop some parts of the theory of compact operators from the point of view of computable analysis. While computable compact operators on Hilbert spaces are easy to understand, it turns out that these operators on Banach spaces are harder to handle. Classically, the theory of compact operators on Banach spaces is developed with the help of the non-constructive tool of sequential compactness. We demonstrate that a substantial amount of this theory can be developed (...) computably on Banach spaces with computable Schauder bases that are well-behaved. The conditions imposed on the bases are such that they generalize the Hilbert space case. In particular, we prove that the space of compact operators on Banach spaces with monotone, computably shrinking, and computable bases is a computable Banach space itself and operations such as composition with bounded linear operators from left are computable. Moreover, we provide a computable version of the Theorem of Schauder on adjoints in this framework and we discuss a non-uniform result on composition with bounded linear operators from right. (shrink)

Quantum probability (QP) theory can be seen as a type of vector symbolic architecture (VSA): mental states are vectors storing structured information and manipulated using algebraic operations. Furthermore, the operations needed by QP match those in other VSAs. This allows existing biologically realistic neural models to be adapted to provide a mechanistic explanation of the cognitive phenomena described in the target article by Pothos & Busemeyer (P&B).

Computational explanations focus on information processing required in specific cognitive capacities, such as perception, reasoning or decision-making. These explanations specify the nature of the information processing task, what information needs to be represented, and why it should be operated on in a particular manner. In this article, the focus is on three questions concerning the nature of computational explanations: What type of explanations they are, in what sense computational explanations are explanatory and to what extent they involve a special, “independent” (...) or “autonomous” level of explanation. In this paper, we defend the view computational explanations are genuine explanations, which track non-causal/formal dependencies. Specifically, we argue that they do not provide mere sketches for explanation, in contrast to what for example Piccinini and Craver :283–311, 2011) suggest. This view of computational explanations implies some degree of “autonomy” for the computational level. However, as we will demonstrate that does not make this view “computationally chauvinistic” in a way that Piccinini or Kaplan :339–373, 2011) have charged it to be. (shrink)

Brain–computer interfaces (BCIs) exemplify a dual-use neurotechnology with significant potential in both civilian and military contexts. While BCIs hold promise for treating neurological conditions such as spinal cord injuries and amyotrophic lateral sclerosis in the future, military decisionmakers in countries such as the United States and China also see their potential to enhance combat capabilities. Some predict that U.S. Special Operations Forces (SOF) will be early adopters of BCI enhancements. This article argues for a shift in focus: the U.S. Special (...) Operations Command (SOCOM) should pursue translational research of medical BCIs for treating severely injured or ill SOF personnel. After two decades of continuous military engagement and on-going high-risk operations, SOF personnel face unique injury patterns, both physical and psychological, which BCI technology could help address. The article identifies six key medical applications of BCIs that could benefit wounded SOF members and discusses the ethical implications of involving SOF personnel in translational research related to these applications. Ultimately, the article challenges the traditional civilian-military divide in neurotechnology, arguing that by collaborating more closely with military stakeholders, scientists can not only help individuals with medical needs, including servicemembers, but also play a role in shaping the future military applications of BCI technology. (shrink)

Each of our theories of mental representation provides some insight into how the mind works. However, these insights often seem incompatible, as the debates between symbolic, dynamical, emergentist, sub-symbolic, and grounded approaches to cognition attest. Mental representations—whatever they are—must share many features with each of our theories of representation, and yet there are few hypotheses about how a synthesis could be possible. Here, I develop a theory of the underpinnings of symbolic cognition that shows how sub-symbolic dynamics may give rise (...) to higher-level cognitive representations of structures, systems of knowledge, and algorithmic processes. This theory implements a version of conceptual role semantics by positing an internal universal representation language in which learners may create mental models to capture dynamics they observe in the world. The theory formalizes one account of how truly novel conceptual content may arise, allowing us to explain how even elementary logical and computational operations may be learned from a more primitive basis. I provide an implementation that learns to represent a variety of structures, including logic, number, kinship trees, regular languages, context-free languages, domains of theories like magnetism, dominance hierarchies, list structures, quantification, and computational primitives like repetition, reversal, and recursion. This account is based on simple discrete dynamical processes that could be implemented in a variety of different physical or biological systems. In particular, I describe how the required dynamics can be directly implemented in a connectionist framework. The resulting theory provides an “assembly language” for cognition, where high-level theories of symbolic computation can be implemented in simple dynamics that themselves could be encoded in biologically plausible systems. (shrink)

Using Type‐2 theory of effectivity, we define computability notions on the spaces of Lebesgue‐integrable functions on the real line that are based on two natural approaches to integrability from measure theory. We show that Fourier transform and convolution on these spaces are computable operators with respect to these representations. By means of the orthonormal basis of Hermite functions in L2, we show the existence of a linear complexity bound for the Fourier transform. (© 2004 WILEY‐VCH Verlag GmbH & (...) Co. KGaA, Weinheim). (shrink)

The issue of proper functioning of operative computing and the utility of program verification, both in general and of specific methods, has been discussed a lot. In many of those discussions, attempts have been made to take mathematics as a model of knowledge and certitude achieving, and accordingly infer about the suitable ways to handle computing. I shortly review three approaches to the subject, and then take a stance by considering social factors which affect the epistemic status of both mathematics (...) and computing. I use the analogy between mathematics and computing in reverse—that is to say, I consider operative computing as a form of making mathematics, and so attempt to learn from computing to mathematics in general. I conclude that mathematics engineering is a field to be both developed for practical improvement of doing mathematics and taken into consideration while philosophizing about mathematics as well. (shrink)

Computational models of infant word‐finding typically operate over transcriptions of infant‐directed speech corpora. It is now possible to test models of word segmentation on speech materials, rather than transcriptions of speech. We propose that such modeling efforts be conducted over the speech of the experimental stimuli used in studies measuring infants' capacity for learning from spoken sentences. Correspondence with infant outcomes in such experiments is an appropriate benchmark for models of infants. We demonstrate such an analysis by applying the DP‐Parser (...) model of Algayres and colleagues to auditory stimuli used in infant psycholinguistic experiments by Pelucchi and colleagues. The DP‐Parser model takes speech as input, and creates multiple overlapping embeddings from each utterance. Prospective words are identified as clusters of similar embedded segments. This allows segmentation of each utterance into possible words, using a dynamic programming method that maximizes the frequency of constituent segments. We show that DP‐Parse mimics American English learners' performance in extracting words from Italian sentences, favoring the segmentation of words with high syllabic transitional probability. This kind of computational analysis over actual stimuli from infant experiments may be helpful in tuning future models to match human performance. (shrink)

Computation is interpretable symbol manipulation. Symbols are objects that are manipulated on the basis of rules operating only on theirshapes, which are arbitrary in relation to what they can be interpreted as meaning. Even if one accepts the Church/Turing Thesis that computation is unique, universal and very near omnipotent, not everything is a computer, because not everything can be given a systematic interpretation; and certainly everything can''t be givenevery systematic interpretation. But even after computers and computation have been successfully distinguished (...) from other kinds of things, mental states will not just be the implementations of the right symbol systems, because of the symbol grounding problem: The interpretation of a symbol system is not intrinsic to the system; it is projected onto it by the interpreter. This is not true of our thoughts. We must accordingly be more than just computers. My guess is that the meanings of our symbols are grounded in the substrate of our robotic capacity to interact with that real world of objects, events and states of affairs that our symbols are systematically interpretable as being about. (shrink)

This paper is a response to Henley who criticizes a previous paper of mine arguing against my claim that computers are devoid of consciousness. While the claim regarding computers and consciousness was not the main theme of my original paper, I do, indeed, subscribe to it. Here, I review the main characteristics of human consciousness presented in the earlier paper and argue that computers cannot exhibit them. Any ascription of these characteristics to computers is superficial and misleading in that it (...) fails to capture essential, intrinsic features of human cognition. More generally, psychological theory couched in terms of semantic representations and the computational operations associated with them is bound to be inadequate. The phenomenology of consciousness is a specific case marking this inadequacy. (shrink)

Brownian computers are supposed to illustrate how logically reversible mathematical operations can be computed by physical processes that are thermodynamically reversible or nearly so. In fact, they are thermodynamically irreversible processes that are the analog of an uncontrolled expansion of a gas into a vacuum.

By the Riesz representation theorem for the dual of C [0; 1], if F: C [0; 1] → ℝ is a continuous linear operator, then there is a function g: [0;1] → ℝ of bounded variation such that F = ∫ f dg . The function g can be normalized such that V = ‖F ‖. In this paper we prove a computable version of this theorem. We use the framework of TTE, the representation approach to computable analysis, (...) which allows to define natural computability for a variety of operators. We show that there are a computable operator S mapping g and an upper bound of its variation to F and a computable operator S ′ mapping F and its norm to some appropriate g. (shrink)

By using interactive computer graphics (ICG), it is possible to discuss the numerical aspects of some arms race issues with more specificity and in a visual way. The number of variables involved in these issues can be quite large; computers operated in the interactive, graphical mode, can allow exploration of the variables, leading to a greater understanding of the issues. This paper will examine some examples of interactive computer graphics: (1) The relationship between silo hardening and the accuracy, yield, and (...) reliability of ICBMs; (2) Target vulnerability (Minuteman, Dense Pack); (3) Counterforce vs. countervalue weapons; (4) Civil defense; (5) Gravitational bias error; (6) MIRV; (7) National vulnerability to a preemptive first strike; (8) Radioactive fallout; and (9) Digital image processing with charge-coupled devices. (shrink)

The use of computers and the role of women in radio astronomy and X-ray crystallography research at the Cavendish Laboratory between 1949 and 1975 have been investigated. We recorded examples of when computers were used, what they were used for and who used them from hundreds of papers published during these years. The use of the EDSAC, EDSAC 2 and TITAN computers was found to increase considerably over this time-scale and they were used for a diverse range of applications. The (...) majority of references to computer operators and programmers referred to women, 57% for astronomy and 62% for crystallography, in contrast to a very small proportion, 4% and 13% respectively, of female authors of papers. (shrink)

In this paper we propose an extension of Defeasible Logic to represent and compute different concepts of defeasible permission. In particular, we discuss some types of explicit permissive norms that work as exceptions to opposite obligations or encode permissive rights. Moreover, we show how strong permissions can be represented both with, and without introducing a new consequence relation for inferring conclusions from explicit permissive norms. Finally, we illustrate how a preference operator applicable to contrary-to-duty obligations can be combined with a (...) new operator representing ordered sequences of strong permissions. The logical system is studied from a computational standpoint and is shown to have linear computational complexity. (shrink)

This work focuses on the application of machine learning techniques to assist the clinicians in the administration of analgesic drug during general anaesthesia. Specifically, the main objective is to propose the basis of an intelligent system capable of making decisions to guide the opioid dose changes based on a new nociception monitor, the analgesia nociception index. Clinical data were obtained from 15 patients undergoing cholecystectomy surgery. By means of an off-line study, machine learning techniques were applied to analyse the possible (...) relationship between the analgesic dose changes performed by the physician due to the hemodynamic activity of the patients and the evolution of the ANI. After training different classifiers and testing the results under cross validation, a preliminary relationship between the evolution of ANI and the dosage of remifentanil was found. These results evidence the potential of the ANI as a promising index to guide the infusion of analgesia. (shrink)

We study the computational complexity of polyadic quantifiers in natural language. This type of quantification is widely used in formal semantics to model the meaning of multi-quantifier sentences. First, we show that the standard constructions that turn simple determiners into complex quantifiers, namely Boolean operations, iteration, cumulation, and resumption, are tractable. Then, we provide an insight into branching operation yielding intractable natural language multi-quantifier expressions. Next, we focus on a linguistic case study. We use computational complexity results to investigate semantic (...) distinctions between quantified reciprocal sentences. We show a computational dichotomy<br>between different readings of reciprocity. Finally, we go more into philosophical speculation on meaning, ambiguity and computational complexity. In particular, we investigate a possibility to<br>revise the Strong Meaning Hypothesis with complexity aspects to better account for meaning shifts in the domain of multi-quantifier sentences. The paper not only contributes to the field of the formal<br>semantics but also illustrates how the tools of computational complexity theory might be successfully used in linguistics and philosophy with an eye towards cognitive science. (shrink)

The theme of this book is formed by a pair of concepts: the concept of formal language as carrier of the precise expression of meaning, facts and problems, and the concept of algorithm or calculus, i.e. a formally operating procedure for the solution of precisely described questions and problems. The book is a unified introduction to the modern theory of these concepts, to the way in which they developed first in mathematical logic and computability theory and later in automata theory, (...) and to the theory of formal languages and complexity theory. Apart from considering the fundamental themes and classical aspects of these areas, the subject matter has been selected to give priority throughout to the new aspects of traditional questions, results and methods which have developed from the needs or knowledge of computer science and particularly of complexity theory. It is both a textbook for introductory courses in the above-mentioned disciplines as well as a monograph in which further results of new research are systematically presented and where an attempt is made to make explicit the connections and analogies between a variety of concepts and constructions. (shrink)

This paper seeks to understand machine cognition. The nature of machine cognition has been shrouded in incomprehensibility. We have often encountered familiar arguments in cognitive science that human cognition is still faintly understood. This paper will argue that machine cognition is far less understood than even human cognition despite the fact that a lot about computer architecture and computational operations is known. Even if there have been putative claims about the transparency of the notion of machine computations, these claims do (...) not hold out in unraveling machine cognition, let alone machine consciousness (if there is any such thing). The nature and form of machine cognition remains further confused also because of attempts to explain human cognition in terms of computation and to model/simulate (aspects of) human cognitive processing in machines. Given that these problems in characterizing machine cognition persist, a view of machine cognition that aims to avoid these problems is outlined. The argument that is advanced is that something becomes a computation in machines only when a human interprets it, which is a kind of semiotic causation. From this it follows that a computing machine is not engaged in a computation unless a human interprets what it is doing; instead, it is engaged in machine cognition, which is defined as a member or subset of the set of all possible mappings of inputs to outputs. The human interpretation, which is a semiotic process, gives meaning to what a machine does, and then what it does becomes a computation. (shrink)

Classical computational modellers of mind urge that the mind is something like a von Neumann computer operating over a system of symbols constituting a language of thought. Such an architecture, they argue, presents us with the best explanation of the compositionality, systematicity and productivity of thought. The language of thought hypothesis is supported by additional independent arguments made popular by Jerry Fodor. Paul Smolensky has developed a connectionist architecture he claims adequately explains compositionality, systematicity and productivity without positing any language (...) of thought, and without positing any operations over a set of symbols. This architecture encodes the information represented in linguistic trees without explicitly representing those trees or their constituents, and indeed without employing any representational vehicles with constituent structure. In a recent article, Fodor (1997; Connectionism and systematicity, Cognition , 62, 109-119) argues that Smolensky's proposal does not work. I defend Smolensky against Fodor's attack, and use this interchange as a vehicle for exploring and criticising the “Language of Thought” hypothesis more generally and the arguments Fodor adduces on its behalf. (shrink)

Currently, there is widespread skepticism that higher cognitive processes, given their apparent flexibility and globality, could be carried out by specialized computational devices, or modules. This skepticism is largely due to Fodor’s influential definition of modularity. From the rather flexible catalogue of possible modular features that Fodor originally proposed has emerged a widely held notion of modules as rigid, informationally encapsulated devices that accept highly local inputs and whose opera- tions are insensitive to context. It is a mistake, however, to (...) equate such features with computational devices in general and therefore to assume, as Fodor does, that higher cognitive processes must be non-computational. Of the many possible non-Fodorean architectures, one is explored here that offers possible solutions to computational problems faced by conventional modular systems: an ‘enzymatic’ architecture. Enzymes are computational devices that use lock-and-key template matching to iden- tify relevant information (substrates), which is then operated upon and returned to a common pool for possible processing by other devices. Highly specialized enzymes can operate together in a common pool of information that is not pre-sorted by information type. Moreover, enzymes can use molecular ‘tags’ to regulate the operations of other devices and to change how particular substrates are construed and operated upon, allowing for highly interactive, context-specific processing. This model shows how specialized, modular processing can occur in an open system, and suggests that skepti- cism about modularity may largely be due to failure to consider alternatives to the standard model. (shrink)

We study vertex operators in 4D conformal field theory derived from quantized gravity, whose dynamics is governed by the Wess-Zumino action by Riegert and the Weyl action. Conformal symmetry is equal to diffeomorphism symmetry in the ultraviolet limit, which mixes positive-metric and negative-metric modes of the gravitational field and thus these modes cannot be treated separately in physical operators. In this paper, we construct gravitational vertex operators such as the Ricci scalar, defined as space-time volume integrals of (...) them are invariant under conformal transformations. Short distance singularities of these operator products are computed and it is shown that their coefficients have physically correct signs. Furthermore, we show that conformal algebra holds even in the system perturbed by the cosmological constant vertex operator as in the case of the Liouville theory shown by Curtright and Thorn. (shrink)

Using P300-based brain–computer interfaces in daily life should take into account the user’s emotional state because various emotional conditions are likely to influence event-related potentials and consequently the performance of P300-based BCIs. This study aimed at investigating whether external emotional stimuli affect the performance of a P300-based BCI, particularly built for controlling home appliances. We presented a set of emotional auditory stimuli to subjects, which had been selected for each subject based on individual valence scores evaluated a priori, while they (...) were controlling an electric light device using a P300-based BCI. There were four conditions regarding the auditory stimuli, including high valence, low valence, noise, and no sound. As a result, subjects controlled the electric light device using the BCI in real time with a mean accuracy of 88.14%. The overall accuracy and P300 features over most EEG channels did not show a significant difference between the four auditory conditions. When we measured emotional states using frontal alpha asymmetry and compared FAA across the auditory conditions, we also found no significant difference. Our results suggest that there is no clear evidence to support a hypothesis that external emotional stimuli influence the P300-based BCI performance or the P300 features while people are controlling devices using the BCI in real time. This study may provide useful information for those who are concerned with the implementation of a P300-based BCI in practice. (shrink)

The sum, difference, product and quotient of two functions with different domains are usually defined only on their common domain. This paper extends these definitions so that the sum and other operations are essentially defined anywhere that at least one of the components is defined. This idea is applied to propositions and events, expressed as indicator functions, to define conditional propositions and conditional events as three-valued indicator functions that are undefined when their condition is false. Extended operations of "and", "or", (...) "not" and "conditioning" are then defined on these conditional events with variable conditions. The probabilities of the disjunction and of the conjunction of two conditionals are expressed in terms of the conditional probabilities of the component conditionals. In a special case, these are shown to be weighted averages of the component conditional probabilities where the weights are the relative probabilities of the various conditions. Next, conditional random variables are defined to be random variables X whose domain has been restricted by a condition on a second random variable Y. The extended sum, difference, product and conditioning operations on functions are then applied to these conditional random variables. The expectation of a random variable and the conditional expectation of a conditional random variable are recounted. Theorem 1 generalizes the standard result that the conditional expectation of the sum of two conditional random variables with disjoint and exhaustive conditions is a weighted sum of the conditional expectations of the component conditional random variables. Because of the extended operations, the theorem is true for arbitrary conditions. Theorem 2 gives a formula for the expectation of the product of two conditional random variables. After the definition of independence of two random variables is extended to accommodate the extended operations, it is applied to the formula of Theorem 2 to simplify the expectation of a product of conditional random variables. Two examples end the paper. The first concerns a work force of n workers of different output levels and work shifts. The second example involves two radars with overlapping surveillance regions and different detection error rates. One radar's error rate is assumed to be sensitive to fog and the other radar's error rate is assumed to be sensitive to air traffic density. The combined error rate over the combined surveillance region given heavy fog and moderate air traffic is computed. (shrink)

We study a theory PTO of polynomial time computability on the type of binary strings, as embedded in full lambda calculus with total application and extensionality. We prove that the closed terms of type W → W are exactly the polynomial time operations. This answers a conjecture of Strahm [13].