Monotonicity and the Expressibility of NP Operators

We investigate why similar extensions of first-order logic using operators (that is, generalized quantifiers) corresponding to NP-complete decision problems apparently differ in expressibility: the logics capture either NP or L^NP. It had been conjectured that the complexity class captured is NP if and only if the operator is monotone. We show that this conjecture is false. However, we provide evidence supporting a revised conjecture involving finite variations of monotone problems. Mathematics Subject Classification: 68Q15, 03D15, 03C13.     

Solving certain singly constrained convex optimization problems in production planning

This paper considers the problem of minimizing a special convex function subject to one linear constraint. Based upon a theorem for lower and upper bounds on the Lagrange multiplier a fully polynomial time approximation scheme is proposed. The efficiency of the algorithm is demonstrated by a computational experiment.     

New directions in scheduling theory

This is an assessment of new developments in the theory of sequencing and scheduling. After a review of recent results and open questions within the traditional class of scheduling problems, we focus on the probabilistic analysis of scheduling algorithms and next discuss some extensions of the traditional problem class that seem to be of particular interest.     

Complexity of linear programming

The complexity of linear programming is discussed in the “integer” and “real number” models of computation. Even though the integer model is widely used in theoretical computer science, the real number model is more useful for estimating an algorithm's running time in actual computation.Although the ellipsoid algorithm is a polynomial-time algorithm in the integer model, we prove that it has unbounded complexity in the real number model. We conjecture that there exists no polynomial-time algorithm for the linear inequalities problem in the real number model. We also conjecture that linear inequalities are strictly harder than linear equalities in all “reasonable” models of computation.     

On End-Extensions of Models of ¬exp

Every model of IΔ₀ is the tally part of a model of the stringlanguage theory Th-FO (a main feature of which consists in having induction on notation restricted to certain AC⁰. sets). We show how to “smoothly” introduce in Th-FO the binary length function, whereby it is possible to make exponential assumptions in models of Th-FO. These considerations entail that every model of IΔ₀ + ¬exp is a proper initial segment of a model of Th-FO and that a modicum of bounded collection is true in these models. Mathematics Subject Classification: 03F30, 03C62, 68Q15.     

Relativistic effects on complexity indexes in atoms in position and momentum spaces

Three different statistical measures of complexity are explored for the atoms He to Ra. The measures are analysed in both position and momentum spaces. Relativistic effects on the complexity indexes are systematically studied. These effects are discussed in terms of the information content factor and the disorder terms of the complexity indexes. Relativistic and non-relativistic complexity indexes are calculated from Optimized Effective Potential densities.     

Finding the Maximal Eigenpair for a Large,Dense,Symmetric Matrix based on Mufa Chen's Algorithm

A hybrid method is presented for determining maximal eigenvalue and its eigenvector(called eigenpair)of a large,dense,symmetric matrix.Many problems require finding only a small part of the eigenpairs,and some require only the maximal one.In a series of papers,efficient algorithms have been developed by Mufa Chen for computing the maximal eigenpairs of tridiagonal matrices with positive off-diagonal elements.The key idea is to explicitly construet effective initial guess of the maximal eigenpair and then to employ a self-closed iterative algorithm.In this paper we will extend Mufa Chen's algorithm to find maximal eigenpair for a large scale,dense,symmetric matrix.Our strategy is to first convert the underlying matrix into the tridiagonal form by using similarity transformations.We then handle the cases that prevent us from applying Chen's algorithm directly,e.g.,the cases with zero or negative super-or sub-diagonal elements.Serval numerical experiments are carried out to demonstrate the efficiency of the proposed hybrid method.     

Modelling pedestrian dynamics into a metro station by thermostatted kinetic theory methods

This paper deals with the modelling of pedestrian dynamics at the entry of a metro station by means of the thermostatted kinetic theory framework. Specifically, the model depicts the time evolution of the pedestrian dynamics at the turnstiles under no panic conditions. The modelling of the microscopic interactions is based on the stochastic game theory and reflects the decision dynamics of the turnstiles pursued by pedestrians. A qualitative analysis is addressed to the equilibrium solutions by means of the classical stability theory of perturbations. Numerical simulations aim at showing the emerging behaviours captured by the model. In particular the model validation is obtained by performing a sensitivity analysis on the parameters and on the initial conditions. Further refinements and research perspective, including the modelling under panic conditions, are discussed in the last section of the paper.