Finite problems and the logic of the weak law of excluded middle

A new characteristic of propositional formulas as operations on finite problems, the cardinality of a sufficient solution set, is defined. It is proved that if a formula is deducible in the logic of the weak law of excluded middle, then the cardinality of a sufficient solution set is bounded by a constant depending only on the number of variables; otherwise, the accessible cardinality of a sufficient solution set is close to (greater than the nth root of) its trivial upper bound. This statement is an analog of the authors result about the algorithmic complexity of sets obtained as values of propositional formulas, which was published previously. Also, we introduce the notion of Kolmogorov complexity of finite problems and obtain similar results.Translated from Matematicheskie Zametki, vol. 77, no. 2, 2005, pp. 291–302.Original Russian Text Copyright © 2005 by A. V. Chernov.This revised version was published online in April 2005 with a corrected issue number.     

Bounds in the weak law of large numbers

We obtain bounds of an asymptotic nature in the weak law of large numbers for sums of random variables without assuming the variables in question have any moments.Translated from Matematicheskie Zametki, Vol. 12, No. 5, pp. 639–642, November, 1972.     

A weak form of interpolation in equational logic

The notions of a weak interpolation property and of weak amalgamation are introduced. It is proved that in varieties with the congruence extension property, the weak interpolation property is equivalent to the weak amalgamation property. In turn, weak amalgamability of a variety is equivalent to amalgamability of a class of finitely generated simple algebras in this variety. Supported by RFBR (grant Nos. 06-01-00358 and 05-01-04003-NNIOa) and by INTAS (grant No. 04-77-7080). __________ Translated from Algebra i Logika, Vol. 47, No. 1, pp. 94–107, January–February, 2008.     

A weak law of large numbers for maxima

A weak law of large numbers related to the classical Gnedenko results for maxima (see Gnedenko, Ann Math 44:423–453, 1943) is established.     

Dual problems for weak and quasi approximation properties

It is shown that for the separable dual X^∗ of a Banach space X if X^∗ has the weak approximation property, then X has the metric quasi approximation property. Using this it is shown that for the separable dual X^∗ of a Banach space X the quasi approximation property and metric quasi approximation property are inherited from X^∗ to X and for a separable and reflexive Banach space X, X having the weak approximation property, bounded weak approximation property, quasi approximation property, metric weak approximation property, and metric quasi approximation property are equivalent. Also it is shown that the weak approximation property, bounded weak approximation property, and quasi approximation property are not inherited from a Banach space X to X^∗.     

Finite convergence analysis and weak sharp solutions for variational inequalities

In this paper, we study the weak sharpness of the solution set of variational inequality problem (in short, VIP) and the finite convergence property of the sequence generated by some algorithm for finding the solutions of VIP. In particular, we give some characterizations of weak sharpness of the solution set of VIP without considering the primal or dual gap function. We establish an abstract result on the finite convergence property for a sequence generated by some iterative methods. We then apply such abstract result to discuss the finite termination property of the sequence generated by proximal point method, exact proximal point method and gradient projection method. We also give an estimate on the number of iterates by which the sequence converges to a solution of the VIP.     

An anytime deduction algorithm for the probabilistic logic and entailment problems

We study two basic problems of probabilistic reasoning: the probabilistic logic and the probabilistic entailment problems. The first one can be defined as follows. Given a set of logical sentences and probabilities that these sentences are true, the aim is to determine whether these probabilities are consistent or not. Given a consistent set of logical sentences and probabilities, the probabilistic entailment problem consists in determining the range of the possible values of the probability associated with additional sentences while maintaining a consistent set of sentences and probabilities.This paper proposes a general approach based on an anytime deduction method that allows the follow-up of the reasoning when checking consistency for the probabilistic logic problem or when determining the probability intervals for the probabilistic entailment problem. Considering a series of subsets of sentences and probabilities, the approach proceeds by computing increasingly narrow probability intervals that either show a contradiction or that contain the tightest entailed probability interval. Computational experience have been conducted to compare the proposed anytime deduction method, called ad-psat with an exact one, psatcol, using column generation techniques, both with respect to the range of the probability intervals and the computing times.     

A quantitative weak law of large numbers and its application to the delta method

Let T _n be a statistic of the form T _n = f(), where is the samplemean of a sequence of independent random variables and f denotes a prescribed function taking values in a separable Banach space. In order to establish asymptotic expansions for bias and variance of T _n conventional theorems typically impose restrictive boundedness conditions upon f or its derivatives; moreover, these conditions are sufficient but not necessary. It is shown that a quantitative version of the weak law of large numbers is both sufficient and necessary for the accuracy of Taylor expansions of T _n . In particular, boundedness conditions may be replaced by mild requirements upon the global growth of f.      

Sensitivity analysis of parametric weak vector equilibrium problems

In this paper, two implicit multifunction theorems are obtained. Then by using a set-valued gap function and the results obtained we study the sensitivity analysis of the solution mapping for a parametric weak vector equilibrium problem and obtain an explicit expression for the contingent derivative of the solution mapping.     

Nonmonotone equilibrium problems: coercivity conditions and weak regularization

We consider a general equilibrium problem in a finite-dimensional space setting and propose a new coercivity condition for existence of solutions. We also show that it enables us to create a broad family of regularization methods with preserving well-definiteness and convergence of the iteration sequence without additional monotonicity assumptions. Some examples of applications are also given.     

Existence of solutions on weak vector equilibrium problems

Weak vector equilibrium problems with bi-variable mappings from product space of two bounded complete locally convex Hausdorff topological vector spaces to another topological vector space are studied. The existence theorems of solutions are proved by the FKKM fixed point theorem. Viscosity principle of vector equilibrium problems is dealt with. The relations between solutions of the vector equilibrium problem and those of its perturbation problem are presented.     

Finite dimensional approximation of nonlinear problems

Summary We begin in this paper the study of a general method of approximation of solutions of nonlinear equations in a Banach space. We prove here an abstract result concerning the approximation of branches of nonsingular solutions. The general theory is then applied to the study of the convergence of two mixed finite element methods for the Navier-Stokes and the von Kármán equations.supported by the Fonds National Suisse de la Recherche Scientifique