The purpose of this study was to determine if task type, task complexity, and search mechanism would have a significant affect on task performance. The problem motivating this study is the potential for systems online help designers to construct systems that can improve the performance of computer users when they need help.

In northern hardwood-conifer forests, alternatives to conventional forest management practices are being developed in order to maintain biodiversity and ecosystem functioning while providing for timber revenue generation. The understory layer of vegetation encompasses the majority of plant species diversity in forested ecosystems and may be sensitive to timber harvest disturbance. Thus, monitoring the response of forest understories to new silvicultural techniques may provide a means for evaluating their intensity. In this study, we hypothesize that i) uneven-aged, low-intensity silvicultural systems can maintain understory plant diversity and support latesuccessional species through harvest disturbance; ii) retaining and enhancing stand structural complexity can increase understory plant diversity in northern hardwoodconifer forests; and iii) plant responses are influenced by interactions between canopy structure, soils, and exogenous climate processes. Experimental treatments include two conventional uneven-aged prescriptions (single-tree selection and group selection) modified to increase structural retention, and a third technique designed to promote late-successional forest structure and function, termed structural complexity enhancement (SCE). Four replications of each treatment were applied to 2 ha management units at three sites in Vermont and New York, U.S.A. Understory vegetation was monitored over 2 years pre- and 4 years post-treatment. We used a linear mixed effects model to evaluate the effects of treatment, soil properties, and drought stress on understory diversity and abundance. Compositional changes among treatments were assessed with non-metric multidimensional scaling (NMS), an ordination technique. Model results show that over time, understory responses were strongly affected by overstory treatment and less influenced by soil chemistry and drought stress. All treatments were successful in maintaining overall composition and diversity. However, late-successional diversity increased significantly in SCE units compared to group selection units. These results indicate that while conventional uneven-aged systems are capable of maintaining understory plant diversity, variations that retain or enhance structural complexity may be more efficient at retaining latesuccessional species. Increased microsite heterogeneity as a result of these techniques may also increase understory plant diversity, at least during the initial post-harvest recovery period.

These compositions explore concepts based on processes and polymeter. Drawing on influences ranging from Steve Reich to Conlon Nancarrow and Nik Bärtsch they use and develop an approach to rhythmic thinking based on ostinati constructed of layers of different speeds. Through the use of click tracks, they look at how an ensemble can be enabled to perform rhythms that, without the electronic support, would be unplayable – crossing a line between the possible and the impossible. By means of processes built on a number of different ideas, the pieces explore how these can be used to affect both the behaviour and evolution of musical material, as well as using them to create fixed structures within which I then move subjectively and more intuitively. The question of balance, of moving between two points or approaches that are seemingly opposites, has also been examined: looking at how the journey affects the destination, where the simple becomes complex, and where personal meets impersonal.

This thesis aims to contribute new understandings of community sustainability through a detailed case study of public sector and community relations within Cornwall. The Look Group Network is a multi-layered public sector and community adult informal learning partnership project which sought to connect Tate St Ives, a national art gallery operating in the far west of the UK, with new audiences. The case study situates together informal learning, community and sustainability and explores their interdependence. The study comprised participant observation with the Look Group members, semi-structured partner interviews, contextual research including a review of the social and political theory of community and an evaluation of relevant sustainable community and informal learning policy. The research aims to identify the underlying conditions which contributed to the sustainability of the Look Groups over a four year period and to assess to what extent these conditions could be transferred to other communities. The original contribution of this project to the existing research literature is in the application of Complexity Theory to empirical data to enable an understanding of the systemic dynamics that contribute to sustainability and in the development of method in the consideration of community and group dynamics.

An online Ramsey game is a game between Builder and Painter, alternating in turns. In each round Builder draws an edge and Painter colors it either red or blue. Builder wins if after some round there is a monochromatic copy of the fixed graph H, otherwise Painter is the winner. In this thesis we investigate the computational complexity of the related decision problem and we show that it is PSPACE-complete. Moreover, we study a version of the game when Builder can draw only planar graphs and a generalization of the game for hypergraphs. We found a new class of graphs unavoidable on planar graphs. We provide a result showing that Builder wins the online Ramsey game on 3-uniform hyperforests when the goal graph H is 1-degenerate. 1

Title: NP search problems Author: Tomáš Jirotka Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajíček, DrSc. Abstract: The thesis summarizes known results in the field of NP search pro- blems. We discuss the complexity of integer factoring in detail, and we propose new results which place the problem in known classes and aim to separate it from PLS in some sense. Furthermore, we define several new search problems. Keywords: Computational complexity, TFNP, integer factorization. 1

We study the complexity of the λ−L(p, q)-labelling problem for fixed λ, p, and q. The task is to assign vertices of a graph labels from the set {0, . . . , λ} such that labels of adjacent vertices differ by at least p while vertices with a common neighbor have different labels. We use two different reductions, one from the NAE-3SAT and the second one from the edge precoloring extension problem. 1

Approved for public release; distribution in unlimited. / The Department of Defense looks increasingly towards an interoperable and integrated system-of-systems to provide required military capability. Non-essential software complexity of a system-of-systems can have a greater negative impact in system behavior than a single system. Our current systems-of-systems tend to require a great deal of software maintenance and to be intolerant of even the most minor of changes with respect to negative perturbations in system behavior. In this thesis, we explore the benefits of developing a conceptual framework as the basis for the system-of-systems development. We examine the application of accepted software engineering practices for single-system developments to the more complex problem of system-of-systems development. Using the Ballistic Missile Defense System as a case study, we present an abstract framework from which we can reason about the system-of-systems. We develop a conceptual software architecture that represents a logical organization of proposed software modules. We map the functionality of the system to conceptual software components with coordination and data exchanges handled by conceptual connectors. Finally, we assess our work to determine the feasibility of applying the conceptual framework techniques described in this thesis to system-of-systems acquisitions with the objective of reducing accidental complexity and controlling essential complexity. / Civilian, Missile Defense Agency, Washington, D.C.

There is much on-going effort to develop new methods for paring down complexity in decision support models (DSM). Many of these methods are so intricate and prone to bias introduction that they are rarely used. The first part of this work developed, tested, and evaluated a new methodology called Knockout (KO) for pruning unnecessary complexity from a Testbed DSM. Complexity is defined as the number of semantic nodes in the DSM. Unnecessary complexity is the maximum quantity of complexity that can be pruned without violating the requisite DSM fidelity. KO identifies all of the semantic nodes that make up the DSM, and determines their individual semantic contribution to DSM fidelity in a manner that avoids bias introduction. The node of least semantic significance to DSM fidelity is always pruned first. KO is shown to efficiently prune complexity from a Testbed DSM, pruning complexity by 36% while reducing fidelity by only 1%. Thus, the first result of this work is a new methodology to enable organizations to trade DSM fidelity for a reduction in DSM complexity. The second part of this work used KO to investigate the ratio of information nodes (parameters) to knowledge nodes (functions) as the complexity of a Testbed DSM was pruned. The a priori expectation was that this work would support one of two learning models in the literature: (1) the bottom-up model known as the Wisdom Hierarchy in which information is accumulated prior to the mental construction of knowledge, or (2) the top-down model known as the Reverse Knowledge Hierarchy in which knowledge is accumulated prior to the mental construction of information. But this work found that the baseline Testbed DSM (the full DSM prior to pruning) has nearly an equal number of information and knowledge nodes (188 to 191), and the ratio of information-to-knowledge remained within a few percent of unity as the DSM's complexity was decreased by successive pruning of the least-semantically-significant node. Thus, the second result of this work is a new model of human goal-driven learning in which information and knowledge accumulate simultaneously and contribute equally to model fidelity and complexity.

We used a divide-and-conquer algorithm to recursively solve the two-dimensional problem of protein folding of an HP sequence with the maximum number of H-H contacts. We derived both lower and upper bounds for the algorithmic complexity by using the newly introduced concept of multi-directional width-bounded geometric separator. We proved that for a grid graph G with n grid points P, there exists a balanced separator A subseteq P$ such that A has less than or equal to 1.02074 sqrt{n} points, and G-A has two disconnected subgraphs with less than or equal to {2over 3}n nodes on each subgraph. We also derive a 0.7555sqrt {n} lower bound for our balanced separator. Based on our multidirectional width-bounded geometric separator, we found that there is an O(n^{5.563sqrt{n}}) time algorithm for the 2D protein folding problem in the HP model. We also extended the upper bound results to rectangular and triangular lattices.