On the Hardness of Computing Intersection,Union and Minkowski Sum of Polytopes

For polytopes P ₁,P ₂⊂ℝ ^d , we consider the intersection P ₁∩P ₂, the convex hull of the union CH(P ₁∪P ₂), and the Minkowski sum P ₁+P ₂. For the Minkowski sum, we prove that enumerating the facets of P ₁+P ₂ is NP-hard if P ₁ and P ₂ are specified by facets, or if P ₁ is specified by vertices and P ₂ is a polyhedral cone specified by facets. For the intersection, we prove that computing the facets or the vertices of the intersection of two polytopes is NP-hard if one of them is given by vertices and the other by facets. Also, computing the vertices of the intersection of two polytopes given by vertices is shown to be NP-hard. Analogous results for computing the convex hull of the union of two polytopes follow from polar duality. All of the hardness results are established by showing that the appropriate decision version, for each of these problems, is NP-complete.     

On effectively computable realizations of choice functions: Dedicated to Professors Kenneth J. Arrow and Anil Nerode

Let X be a compact, convex subset of R_n, and let $\text{〈R(X),}\text{F}{}_{\mathrm{R}}\text{〉}$ be a recursive space of alternatives, where R(X) is the image of X in a recursive metric space, and $\text{F}{}_{\mathrm{R}}$ is the family of all recursive subsets of R(X). If $\text{C:}\text{F}{}_{\mathrm{R}}\text{→}\text{F}{}_{\mathrm{R}}$ is a non-trivial recursively representable choice function that is rational in the sense of Richter, we prove that C has no recursive realization within Church's Thesis. Our proof is not a diagonalization argument and uses no paradoxical statements from formal systems. Instead, the proof is a Kleene-Post reduction style argument and uses the Turing equivalence between mechanical devices of computation and the recursive functions of Gödel and Kleene.     

Pattern formation in the thiourea-iodate-sulfite system: Spatial bistability, waves, and stationary patterns

We present a detailed study of the reaction-diffusion patterns observed in the thiourea-iodate-sulfite (TuIS) reaction, operated in open one-side-fed reactors. Besides spatial bistability and spatio-temporal oscillatory dynamics, this proton autoactivated reaction shows stationary patterns, as a result of two back-to-back Turing bifurcations, in the presence of a low-mobility proton binding agent (sodium polyacrylate). This is the third aqueous solution system to produce stationary patterns and the second to do this through a Turing bifurcation. The stationary pattern forming capacities of the reaction are explored through a systematic design method, which is applicable to other bistable and oscillatory reactions. The spatio-temporal dynamics of this reaction is compared with that of the previous ferrocyanide-iodate-sulfite mixed Landolt system.     

Turing vegetation patterns in a generalized hyperbolic Klausmeier model

The formation of Turing vegetation patterns in flat arid environments is investigated in the framework of a generalized version of the hyperbolic Klausmeier model. The extensions here considered involve, on the one hand, the strength of the rate at which rainfall water enters into the soil and, on the other hand, the functional dependence of the inertial times on vegetation biomass and soil water. The study aims at elucidating how the inclusion of these generalized quantities affects the onset of bifurcation of supercritical Turing patterns as well as the transient dynamics observed from an uniformly vegetated state towards a patterned state. To achieve these goals, linear and multiple-scales weakly nonlinear stability analysis are addressed, this latter being inspected in both large and small spatial domains. Analytical results are then corroborated by numerical simulations, which also serve to describe more deeply the spatio-temporal evolution of the emerging patterns as well as to characterize the different timescales involved in vegetation dynamics.     

Spatiotemporal dynamics of a predator-prey model incorporating a prey refuge

In this paper, we investigate the spatiotemporal dynamics of a ratio-dependent predator-prey model with cross diffusion incorporating proportion of prey refuge. First we get the critical lines of Hopf and Turing bifurcations in a spatial domain by using mathematical theory. More specifically, the exact Turing region is given in a two parameter space. Also we perform a series of numerical simulations. The obtained results reveal that this system has rich dynamics, such as spotted, stripe and labyrinth patterns which show that it is useful to use the predator-prey model to reveal the spatial dynamics in the real world.     

Spatiotemporal dynamics in a predator-prey model with a functional response increasing in both predator and prey densities

In this paper, we studied a diffusive predator-prey model with a functional response increasing in both predator and prey densities. The Turing instability and local stability are studied by analyzing the eigenvalue spectrum. Delay induced Hopf bifurcation is investigated by using time delay as bifurcation parameter. Some conditions for determining the property of Hopf bifurcation are obtained by utilizing the normal form method and center manifold reduction for partial functional differential equation.     

Spatial resonance and Turing–Hopf bifurcations in the Gierer–Meinhardt model

Gierer–Meinhardt system as a molecularly plausible model has been proposed to formalize the observation for pattern formation. In this paper, the Gierer–Meinhardt model without the saturating term is considered. By the linear stability analysis, we not only give out the conditions ensuring the stability and Turing instability of the positive equilibrium but also find the parameter values where possible Turing–Hopf and spatial resonance bifurcation can occur. Then we develop the general algorithm for the calculations of normal form associated with codimension-2 spatial resonance bifurcation to better understand the dynamics neighboring of the bifurcating point. The spatial resonance bifurcation reveals the interaction of two steady state solutions with different modes. Numerical simulations are employed to illustrate the theoretical results for both the Turing–Hopf bifurcation and spatial resonance bifurcation. Some expected solutions including stable spatially inhomogeneous periodic solutions and coexisting stable spatially steady state solutions evolve from Turing–Hopf bifurcation and spatial resonance bifurcation respectively.     

Post's Problem for Reducibilities of Bounded Complexity

In this paper we consider the we known method by E. Post of solving the problem of construction of recursively enumerable sets that have a degree intermediate between the degrees of recursive and complete sets with respect to a given reducibility. Post considered reducibilities ≤_m, ≤_btt, ≤_tt and ≤_T and solved the problem for al of them except ≤_T. Here we extend Post's original method of construction of incomplete sets onto two wide classes of sub‐Turing reducibilities what were studying in [1, 2].