Algorithmic Complexity and Computability

High-level introduction for web science students, rather than for computer science students.

Complexity of Monte Carlo algorithms for a class of integral equations

In this work we study the computational complexity of a class of grid Monte Carlo algorithms for integral equations. The idea of the algorithms consists in an approximation of the integral equation by a system of algebraic equations. Then the Markov chain iterative Monte Carlo is used to solve the system. The assumption here is that the corresponding Neumann series for the iterative matrix does not necessarily converge or converges slowly. We use a special technique to accelerate the convergence. An estimate of the computational complexity of Monte Carlo algorithm using the considered approach is obtained. The estimate of the complexity is compared with the corresponding quantity for the complexity of the grid-free Monte Carlo algorithm. The conditions under which the class of grid Monte Carlo algorithms is more efficient are given.

Dealing with complexity: an overview of the neural network approach

The problem of complexity is particularly relevant to the field of control engineering, since many engineering problems are inherently complex. The inherent complexity is such that straightforward computational problem solutions often produce very poor results. Although parallel processing can alleviate the problem to some extent, it is artificial neural networks (in various forms) which have recently proved particularly effective, even in dealing with the causes of the problem itself. This paper presents an overview of the current neural network research being undertaken. Such research aims to solve the complex problems found in many areas of science and engineering today.

Effective communication to improve udder health: can social science help?

Improved udder health requires consistent application of appropriate management practices by those involved in managing dairy herds and the milking process. Designing effective communication requires that we understand why dairy herd managers behave in the way they do and also how the means of communication can be used both to inform and to influence. Social sciences- ranging from economics to anthropology - have been used to shed light on the behaviour of those who manage farm animals. Communication science tells us that influencing behaviour is not simply a question of „getting the message across‟ but of addressing the complex of factors that influence an individual‟s behavioural decisions. A review of recent studies in the animal health literature shows that different social science frameworks and methodologies offer complementary insights into livestock managers‟ behaviour but that the diversity of conceptual and methodological frameworks presents a challenge for animal health practitioners and policy makers who seek to make sense of the findings – and for researchers looking for helpful starting points. Data from a recent study in England illustrate the potential of „home-made‟ conceptual frameworks to help unravel the complexity of farmer behaviour. At the same time, though, the data indicate the difficulties facing those designing communication strategies in a context where farmers believe strongly that they are already doing all they can reasonably be expected to do to minimise animal health risks.

Complexity theory and planning: examining 'fractals' for organising policy domains in planning practice

This article examines selected methodological insights that complexity theory might provide for planning. In particular, it focuses on the concept of fractals and, through this concept, how ways of organising policy domains across scales might have particular causal impacts. The aim of this article is therefore twofold: (a) to position complexity theory within social science through a ‘generalised discourse’, thereby orienting it to particular ontological and epistemological biases and (b) to reintroduce a comparatively new concept – fractals – from complexity theory in a way that is consistent with the ontological and epistemological biases argued for, and expand on the contribution that this might make to planning. Complexity theory is theoretically positioned as a neo-systems theory with reasons elaborated. Fractal systems from complexity theory are systems that exhibit self-similarity across scales. This concept (as previously introduced by the author in ‘Fractal spaces in planning and governance’) is further developed in this article to (a) illustrate the ontological and epistemological claims for complexity theory, and to (b) draw attention to ways of organising policy systems across scales to emphasise certain characteristics of the systems – certain distinctions. These distinctions when repeated across scales reinforce associated processes/values/end goals resulting in particular policy outcomes. Finally, empirical insights from two case studies in two different policy domains are presented and compared to illustrate the workings of fractals in planning practice.

The oscillatory bioelectrical signal from plants explained by a simulated electrical model and tested using Lempel-Ziv complexity

This paper demonstrates the oscillatory characteristics of electrical signals acquired from two ornamental plant types (Epipremnum pinnatum and Philodendron scandens - Family Araceae), using a noninvasive acquisition system. The electrical signal was recorded using Ag/AgCl superficial electrodes inside a Faraday cage. The presence of the oscillatory electric generator was shown using a classical power spectral density. The Lempel and Ziv complexity measurement showed that the plant signal was not noise despite its nonlinear behavior. The oscillatory characteristics of the signal were explained using a simulated electrical model that establishes that for a frequency range from 5 to 15 Hz, the oscillatory characteristic is higher than for other frequency ranges. All results show that non-invasive electrical plant signals can be acquired with improvement of signal-to-noise ratio using a Faraday cage, and a simple electrical model is able to explain the electrical signal being generated. (C) 2010 Elsevier B.V. All rights reserved.

Medical image retrieval based on complexity analysis

Texture is one of the most important visual attributes used in image analysis. It is used in many content-based image retrieval systems, where it allows the identification of a larger number of images from distinct origins. This paper presents a novel approach for image analysis and retrieval based on complexity analysis. The approach consists of a texture segmentation step, performed by complexity analysis through BoxCounting fractal dimension, followed by the estimation of complexity of each computed region by multiscale fractal dimension. Experiments have been performed with MRI database in both pattern recognition and image retrieval contexts. Results show the accuracy of the method and also indicate how the performance changes as the texture segmentation process is altered.

Essays on decision sciences: exploring cognition, information processing, and complexity

This thesis provides three original contributions to the field of Decision Sciences. The first contribution explores the field of heuristics and biases. New variations of the Cognitive Reflection Test (CRT--a test to measure "the ability or disposition to resist reporting the response that first comes to mind"), are provided. The original CRT (S. Frederick [2005] Journal of Economic Perspectives, v. 19:4, pp.24-42) has items in which the response is immediate--and erroneous. It is shown that by merely varying the numerical parameters of the problems, large deviations in response are found. Not only the final results are affected by the proposed variations, but so is processing fluency. It seems that numbers' magnitudes serve as a cue to activate system-2 type reasoning. The second contribution explores Managerial Algorithmics Theory (M. Moldoveanu [2009] Strategic Management Journal, v. 30, pp. 737-763); an ambitious research program that states that managers display cognitive choices with a "preference towards solving problems of low computational complexity". An empirical test of this hypothesis is conducted, with results showing that this premise is not supported. A number of problems are designed with the intent of testing the predictions from managerial algorithmics against the predictions of cognitive psychology. The results demonstrate (once again) that framing effects profoundly affect choice, and (an original insight) that managers are unable to distinguish computational complexity problem classes. The third contribution explores a new approach to a computationally complex problem in marketing: the shelf space allocation problem (M-H Yang [2001] European Journal of Operational Research, v. 131, pp.107--118). A new representation for a genetic algorithm is developed, and computational experiments demonstrate its feasibility as a practical solution method. These studies lie at the interface of psychology and economics (with bounded rationality and the heuristics and biases programme), psychology, strategy, and computational complexity, and heuristics for computationally hard problems in management science.

Evolutionary Changes in the Complexity of the Tectum of Nontetrapods: A Cladistic Approach

Background: The tectum is a structure localized in the roof of the midbrain in vertebrates, and is taken to be highly conserved in evolution. The present article assessed three hypotheses concerning the evolution of lamination and citoarchitecture of the tectum of nontetrapod animals: 1) There is a significant degree of phylogenetic inertia in both traits studied (number of cellular layers and number of cell classes in tectum); 2) Both traits are positively correlated accross evolution after correction for phylogeny; and 3) Different developmental pathways should generate different patterns of lamination and cytoarchitecture.Methodology/Principal Findings: The hypotheses were tested using analytical-computational tools for phylogenetic hypothesis testing. Both traits presented a considerably large phylogenetic signal and were positively associated. However, no difference was found between two clades classified as per the general developmental pathways of their brains.Conclusions/Significance: The evidence amassed points to more variation in the tectum than would be expected by phylogeny in three species from the taxa analysed; this variation is not better explained by differences in the main course of development, as would be predicted by the developmental clade hypothesis. Those findings shed new light on the evolution of an functionally important structure in nontetrapods, the most basal radiations of vertebrates.