A Short History of Computational Complexity

National Science Foundation (CCR-998310); Army Research Office (DAAD19-02-1-0058)

On the Complexity of Quantum ACC

For any q > 1, let MOD_q be a quantum gate that determines if the number of 1's in the input is divisible by q. We show that for any q,t > 1, MOD_q is equivalent to MOD_t (up to constant depth). Based on the case q=2, Moore has shown that quantum analogs of AC^(0), ACC[q], and ACC, denoted QAC^(0)_wf, QACC[2], QACC respectively, define the same class of operators, leaving q > 2 as an open question. Our result resolves this question, implying that QAC^(0)_wf = QACC[q] = QACC for all q. We also prove the first upper bounds for QACC in terms of related language classes. We define classes of languages EQACC, NQACC (both for arbitrary complex amplitudes) and BQACC (for rational number amplitudes) and show that they are all contained in TC^(0). To do this, we show that a TC^(0) circuit can keep track of the amplitudes of the state resulting from the application of a QACC operator using a constant width polynomial size tensor sum. In order to accomplish this, we also show that TC^(0) can perform iterated addition and multiplication in certain field extensions.

Study abroad and complexity, accuracy and fluency (CAF) development: a longitudinal investigation of French and Chinese Learners of L2 English

This longitudinal study tracked third-level French (n=10) and Chinese (n=7) learners of English as a second language (L2) during an eight-month study abroad (SA) period at an Irish university. The investigation sought to determine whether there was a significant relationship between length of stay (LoS) abroad and gains in the learners' oral complexity, accuracy and fluency (CAF), what the relationship was between these three language constructs and whether the two learner groups would experience similar paths to development. Additionally, the study also investigated whether specific reported out-of-class contact with the L2 was implicated in oral CAF gains. Oral data were collected at three equidistant time points; at the beginning of SA (T1), midway through the SA sojourn (T2) and at the end (T3), allowing for a comparison of CAF gains arising during one semester abroad to those arising during a subsequent semester. Data were collected using Sociolinguistic Interviews (Labov, 1984) and adapted versions of the Language Contact Profile (Freed et al., 2004). Overall, the results point to LoS abroad as a highly influential variable in gains to be expected in oral CAF during SA. While one semester in the TL country was not enough to foster statistically significant improvement in any of the CAF measures employed, significant improvement was found during the second semester of SA. Significant differences were also revealed between the two learner groups. Finally, significant correlations, some positive, some negative, were found between gains in CAF and specific usage of the L2. All in all, the disaggregation of the group data clearly illustrates, in line with other recent enquiries (e.g. Wright and Cong, 2014) that each individual learner's path to CAF development was unique and highly individualised, thus providing strong evidence for the recent claim that SLA is "an individualized nonlinear endeavor" (Polat and Kim, 2014: 186).

Complexity of mixed shop scheduling problems: A survey

We survey recent results on the computational complexity of mixed shop scheduling problems. In a mixed shop, some jobs have fixed machine orders (as in the job shop), while the operations of the other jobs may be processed in arbitrary order (as in the open shop). The main attention is devoted to establishing the boundary between polynomially solvable and NP-hard problems. When the number of operations per job is unlimited, we focus on problems with a fixed number of jobs.

Coastal Zone Ecosystem Services: From science to values and decision making; a case study

This research is concerned with the following environmental research questions: socio-ecological system complexity, especially when valuing ecosystem services; ecosystems stock and services flow sustainability and valuation; the incorporation of scale issues when valuing ecosystem services; and the integration of knowledge from diverse disciplines for governance and decision making. In this case study, we focused on ecosystem services that can be jointly supplied but independently valued in economic terms: healthy climate (via carbon sequestration and storage), food (via fisheries production in nursery grounds), and nature recreation (nature watching and enjoyment). We also explored the issue of ecosystem stock and services flow, and we provide recommendations on how to value stock and flows of ecosystem services via accounting and economic values respectively. We considered broadly comparable estuarine systems located on the English North Sea coast: the Blackwater estuary and the Humber estuary. In the past, these two estuaries have undergone major land-claim. Managed realignment is a policy through which previously claimed intertidal habitats are recreated allowing the enhancement of the ecosystem services provided by saltmarshes. In this context, we investigated ecosystem service values, through biophysical estimates and welfare value estimates. Using an optimistic (extended conservation of coastal ecosystems) and a pessimistic (loss of coastal ecosystems because of, for example, European policy reversal) scenario, we find that context dependency, and hence value transfer possibilities, vary among ecosystem services and benefits. As a result, careful consideration in the use and application of value transfer, both in biophysical estimates and welfare value estimates, is advocated to supply reliable information for policy making.

Performance Management in the UK Public Sector: addressing multiple stakeholder complexity

Purpose The aim of this paper is to explore the issues involved in developing and applying performance management approaches within a large UK public sector department using a multiple stakeholder perspective and an accompanying theoretical framework. Design/methodology/approach An initial short questionnaire was used to determine perceptions about the implementation and effectiveness of the new performance management system across the organisation. In total, 700 questionnaires were distributed. Running concurrently with an ethnographic approach, and informed by the questionnaire responses, was a series of semi-structured interviews and focus groups. Findings Staff at all levels had an understanding of the new system and perceived it as being beneficial. However, there were concerns that the approach was not continuously managed throughout the year and was in danger of becoming an annual event, rather than an ongoing process. Furthermore, the change process seemed to have advanced without corresponding changes to appraisal and reward and recognition systems. Thus, the business objectives were not aligned with motivating factors within the organisation. Research limitations/implications Additional research to test the validity and usefulness of the theoretical model, as discussed in this paper, would be beneficial. Practical implications The strategic integration of the stakeholder performance measures and scorecards was found to be essential to producing an overall stakeholder-driven strategy within the case study organisation. Originality/value This paper discusses in detail the approach adopted and the progress made by one large UK public sector organisation, as it attempts to develop better relationships with all of its stakeholders and hence improve its performance. This paper provides a concerted attempt to link theory with practice.

Art, biology and technology. Interdisciplinary relations in the science lab

Bio art, understood as the convergence of the relations between art, biology and technology, constitutes a useful case study to discuss the meaning of interdisciplinarity in the artistic field. This paper explores different discourses around interdisciplinarity in order to challenge certain generic approaches for their ineffectiveness when assessing artistic practices. It is proposed that the analysis of interdisciplinarity must address the singular connections produced in the artistic practice itself, considering the impossibility of reducing the complexity of interdisciplinary dialogues into generic considerations. Taking bioart as a case study, different kinds of relationships between the artist and the lab are identified and analyzed, ranging from the use of the lab as a true atelier and as a resource for materials and techniques, to the rejection of the lab by proposing amateurism as an alternative. estrategias amateur, pasando por su utilización como fuente de técnicas y materiales.

Potential roles for differential body size and microhabitat complexity in mediating biotic interactions within invasive freshwater amphipod assemblages

Cannibalism and intraguild predation (IGP) are common amongst freshwater amphipod crustacean aswsemblages, particularly between individuals of different body size, with IGP of smaller by larger species. The decline of Gammarus tigrinus Populations in mainland Europe has been accompanied by the arrival of the Ponto-Caspian invader Dikerogammarus villosus and previous studies have implicated IGP of G. tigrinus by the larger D. villosus as the principal driving force in this replacement. We examined how factors such as microhabitat and body size may mediate both cannibalism within G. tigrinus populations and IGP by D. villosus and thus contribute to field patterns of coexistence and exclusion. A field Survey of an invaded Dutch fake indicated that G. tigrinus and D. villosus differed in distribution. with D. villosus being the numerically dominant amphipod (80-96 %) on the rocky boulder Substrate of the shoreline and G. tigrinus being the dominant amphipod (100 %) in the crushed shell/sand matrix immediately adjacent to this. Laboratory microcosm experiments indicated that G. tigrinus cannibalism, particularly of smaller by larger size classes, may be common. In addition, although D. villosus predation of all G. tigrinus size classes was extreme, the smallest size classes Suffered the highest predation. Indeed, when exposed to D. villosus, predation of larger G. tigrinus was lowest when smaller G. tigrinus were also present. Increasing microhabitat complexity from a simple bare substrate littered with Dreissena polymorpha zebra mussels to a Crushed shell/sand matrix significantly reduced both cannibalism and IGP. Our Study emphasizes the need to consider both life history stages and habitat template, when considering the impacts of biotic interactions and it also emphasizes that complex, interacting factors may be mediating the range expansion of D. villosus.

The Critical Reading of the Images Associated with Science-Related News Reports: Establishing a knowledge, skills, and attitudes framework

For the majority of adults, the media constitute their main source of information about science and science-related matters impacting on society. To help prepare young people to engage with science in the media, teachers are being exhorted to equip their students with the knowledge, skills, and attitudes to respond critically to science-related news reports. Typically, such reports comprise not only text, but also visual elements. These images are not simply adjuncts to the written word; they are integral to meaning-making. Though science teachers make considerable use of newspaper images, they tend to view these representations unproblematically, underestimating their potential ambiguity, complexity, and role in framing media messages. They rarely aim to develop students’ ability to ‘read’, critically, such graphics. Moreover, research into how this might be achieved is limited and, consequently, research-informed guidance which could support this instruction is lacking. This paper describes a study designed to formulate a framework for such teaching. Science communication scholars, science journalists and media educators with acknowledged relevant expertise were surveyed to ascertain what knowledge, skills, and attitudes they deemed useful to engagement with science related news images. Their proposals were recast as learning intentions (instructional objectives), and science and English teachers collaborated to suggest which could be addressed with secondary school students and the age group best suited to their introduction. The outcome is an inventory of learning intentions on which teachers could draw to support their planning of instructional sequences aimed at developing students’ criticality in respect of the totality of science news reports.

Functional responses of the intertidal amphipod Echinogammarus marinus: effects of prey supply, model selection and habitat complexity.

The influence of predation in structuring ecological communities can be informed by examining the shape and magnitude of the functional response of predators towards prey. We derived functional responses of the ubiquitous intertidal amphipod Echinogammarus marinus towards one of its preferred prey species, the isopod Jaera nordmanni. First, we examined the form of the functional response where prey were replaced following consumption, as compared to the usual experimental design where prey density in each replicate is allowed to deplete. E. marinus exhibited Type II functional responses, i.e. inversely density-dependent predation of J. nordmanni that increased linearly with prey availability at low densities, but decreased with further prey supply. In both prey replacement and non-replacement experiments, handling times and maximum feeding rates were similar. The non-replacement design underestimated attack rates compared to when prey were replaced. We then compared the use of Holling’s disc equation (assuming constant prey density) with the more appropriate Rogers’ random predator equation (accounting for prey depletion) using the prey non-replacement data. Rogers’ equation returned significantly greater attack rates but lower maximum feeding rates, indicating that model choice has significant implications for parameter estimates. We then manipulated habitat complexity and found significantly reduced predation by the amphipod in complex as opposed to simple habitat structure. Further, the functional response changed from a Type II in simple habitats to a sigmoidal, density-dependent Type III response in complex habitats, which may impart stability on the predator−prey interaction. Enhanced habitat complexity returned significantly lower attack rates, higher handling times and lower maximum feeding rates. These findings illustrate the sensitivity of the functional response to variations in prey supply, model selection and habitat complexity and, further, that E. marinus could potentially determine the local exclusion and persistence of prey through habitat-mediated changes in its predatory functional responses.

Holocene tephras highlight complexity of volcanic signals in Greenland ice cores

Acidity peaks in Greenland ice cores have been used as critical reference horizons for synchronizing ice core records, aiding the construction of a single Greenland Ice Core Chronology (GICC05) for the Holocene. Guided by GICC05, we examined sub-sections of three Greenland cores in the search for tephra from specific eruptions that might facilitate the linkage of ice core records, the dating of prehistoric tephras and the understanding of the eruptions. Here we report the identification of 14 horizons with tephra particles, including 11 that have not previously been reported from the North Atlantic region and that have the potential to be valuable isochrons. The positions of tephras whose major element data are consistent with ash from the Katmai AD 1912 and Öraefajökull AD 1362 eruptions confirm the annually resolved ice core chronology for the last 700 years. We provide a more refined date for the so-called “AD860B” tephra, a widespread isochron found across NW Europe, and present new evidence relating to the 17th century BC Thera/Aniakchak debate that shows N. American eruptions likely contributed to the acid signals at this time. Our results emphasize the variable spatial and temporal distributions of volcanic products in Greenland ice that call for a more cautious approach in the attribution of acid signals to specific eruptive events.

Functional Complexity: The source of value in biodiversity.

Biodiversity may be seen as a scientific measure of the complexity of a biological system, implying an information basis. Complexity cannot be directly valued, so economists have tried to define the services it provides, though often just valuing the services of 'key' species. Here we provide a new definition of biodiversity as a measure of functional information, arguing that complexity embodies meaningful information as Gregory Bateson defined it. We argue that functional information content (FIC) is the potentially valuable component of total (algorithmic) information content (AIC), as it alone determines biological fitness and supports ecosystem services. Inspired by recent extensions to the Noah's Ark problem, we show how FIC/AIC can be calculated to measure the degree of substitutability within an ecological community. Establishing substitutability is an essential foundation for valuation. From it, we derive a way to rank whole communities by Indirect Use Value, through quantifying the relation between system complexity and the production rate of ecosystem services. Understanding biodiversity as information evidently serves as a practical interface between economics and ecological science. © 2012 Elsevier B.V.

Multi-Modal CTL:Completeness, Complexity, and an Application

We define a multi-modal version of Computation Tree Logic (ctl) by extending the language with path quantifiers E and A where d denotes one of finitely many dimensions, interpreted over Kripke structures with one total relation for each dimension. As expected, the logic is axiomatised by taking a copy of a ctl axiomatisation for each dimension. Completeness is proved by employing the completeness result for ctl to obtain a model along each dimension in turn. We also show that the logic is decidable and that its satisfiability problem is no harder than the corresponding problem for ctl. We then demonstrate how Normative Systems can be conceived as a natural interpretation of such a multi-dimensional ctl logic. © 2009 Springer Science+Business Media B.V.