On the bounded version of Hilbert's tenth problem

 The paper establishes lower bounds on the provability of 𝒟=NP and the MRDP theorem in weak fragments of arithmetic. The theory I ⁵ E ₁ is shown to be unable to prove 𝒟=NP. This non-provability result is used to show that I ⁵ E ₁ cannot prove the MRDP theorem. On the other hand it is shown that I ¹ E ₁ proves 𝒟 contains all predicates of the form (∀i≤|b|)P(i,x)^Q(i,x) where ^ is =, <, or ≤, and I ⁰ E ₁ proves 𝒟 contains all predicates of the form (∀i≤b)P(i,x)=Q(i,x). Here P and Q are polynomials. A conjecture is made that 𝒟 contains NLOGTIME. However, it is shown that this conjecture would not be sufficient to imply 𝒟=N P. Weak reductions to equality are then considered as a way of showing 𝒟=NP. It is shown that the bit-wise less than predicate, ≤₂, and equality are both co-NLOGTIME complete under FDLOGTIME reductions. This is used to show that if the FDLOGTIME functions are definable in 𝒟 then 𝒟=N P. Received: 13 July 2001 / Revised version: 9 April 2002 / Published online: 19 December 2002 Key words or phrases: Bounded Arithmetic – Bounded Diophantine Complexity     

The weak pigeonhole principle for function classes in S 12

It is well known that S ¹₂ cannot prove the injective weak pigeonhole principle for polynomial time functions unless RSA is insecure. In this note we investigate the provability of the surjective (dual) weak pigeonhole principle in S ¹₂ for provably weaker function classes. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Uniqueness,Extinction and Explosivity of Generalised Markov Branching Processes with Pairwise Interaction

We examine basic properties regarding uniqueness, extinction, and explosivity for the generalised Markov branching processes with pairwise interaction. First we establish uniqueness criteria, proving that in the essentially-explosive case the process is honest if and only if the mean death rate is greater than or equal to the mean birth rate, while in the sub-explosive case the process is dishonest only in exceptional circumstances. Explicit expressions are then obtained for the extinction probabilities, the mean extinction times and the conditional mean extinction times. Explosivity is also investigated and an explicit expression for mean explosion time is established.     

Quasi-Stationarity of Discrete-Time Markov Chains with Drift to Infinity

We consider a discrete-time Markov chain on the non-negative integers with drift to infinity and study the limiting behavior of the state probabilities conditioned on not having left state 0 for the last time. Using a transformation, we obtain a dual Markov chain with an absorbing state such that absorption occurs with probability 1. We prove that the state probabilities of the original chain conditioned on not having left state 0 for the last time are equal to the state probabilities of its dual conditioned on non-absorption. This allows us to establish the simultaneous existence, and then equivalence, of their limiting conditional distributions. Although a limiting conditional distribution for the dual chain is always a quasi-stationary distribution in the usual sense, a similar statement is not possible for the original chain.     

Total variation approximation for quasi-equilibrium distributions,II

Quasi-stationary distributions have been used in biology to describe the steady state behaviour of Markovian population models which, while eventually certain to become extinct, nevertheless maintain an apparent stochastic equilibrium for long periods. However, they have substantial drawbacks; a Markov process may not possess any, or may have several, and their probabilities can be very difficult to determine. Here, we consider conditions under which an apparent stochastic equilibrium distribution can be identified and computed, irrespective of whether a quasi-stationary distribution exists, or is unique; we call it a quasi-equilibrium distribution. The results are applied to multi-dimensional Markov population processes.     

The determination of quasistationary distributions directly from the transition rates of an absorbing Markov chain

There are many stochastic systems arising in areas as diverse as wildlife management, chemical kinetics and reliability theory, which eventually “die out,” yet appear to be stationary over any reasonable time scale. The notion of a quasistationary distribution has proved to be a potent tool in modelling this behaviour. In finite-state systems the existence of a quasistationary distribution is guaranteed. However, in the infinite-state case this may not always be so and the question of whether or not quasistationary distributions exist requires delicate mathematical analysis. The purpose of this paper is to present simple conditions for the existence of quasistationary distributions for continuous-time Markov chains and to demonstrate how these can be applied in practice.     

Ordinal notations and well-orderings in bounded arithmetic

This paper investigates provability and non-provability of well-foundedness of ordinal notations in weak theories of bounded arithmetic. We define a notion of well-foundedness on bounded domains. We show that T₂¹ and S₂² can prove the well-foundedness on bounded domains of the ordinal notations below ₀ and Γ₀. As a corollary, the class of polynomial local search problems, PLS, can be augmented with cost functions that take ordinal values below ₀ and Γ₀ without increasing the class PLS.