A modification of the decoding q-ary Sum Product Algorithm (q-SPA) was proposed for the nonbinary codes with small check density based on the permutation matrices. The algorithm described has a vector realization and operates over the vectors defined on the field GF(q), rather than over individual symbols. Under certain code parameters, this approach enables significant speedup of modeling.
We show the results of a statistical study of the complexity of the asymmetric traveling salesman problem (ATSP) obtained by processing a specially generated pool of matrices. We show that the normal distribution can serve as an approximation to the distribution of the logarithm of complexity for a fixed problem dimension. We construct a family of probability distributions that represent satisfactory approximations of the complexity distribution with a dimension of the cost matrix from 20 to 49. Our main objective is to make probabilistic predictions of the complexity of individual problems for larger values of the dimension of the cost matrix. We propose a representation of the complexity distribution that makes it possible to predict the complexity. We formulate the unification hypothesis and show directions for further study, in particular proposals on the task of clustering “complex” and “simple” ATSP problems and proposals on the task of directly predicting the complexity of a specific problem instance based on the initial cost matrix.
The model of a channel that describes the transmission of information in communication systems with a single-user receiver based on order statistics is considered. The transmission of information through such a channel using a linear block code is studied. The aim of this paper is to find an upper bound on error probability for the case in which exhaustive search and a given decoding criterion are used.
The result on existence of a pure-strategy symmetric Bayesian Nash equilibrium in the war of attrition is generalized for fuzzy players' actions and types.
When a society needs to make a collective decision one could apply some aggregation method, particularly, voting. One of the main problems with voting is the manipulability of voting rules. We say a social choice rule is vulnerable to manipulation if there exists at least one voter who can achieve a better voting result by misrepresenting her preferences. The popular approach to comparing manipulability of social choice rules is defining a complexity class of the corresponding manipulation problem. This paper provides a survey into manipulation complexity literature considering variety of problems with different assumptions and constraints.
. Abstract—We show the graphical and algebraic counterparts of Kharitonov’s theorem constructed on the foundation of the robust Nyquist criterion. The graphical counterpart is different from Tsypkin–Polyak hodograph.
Consideration was given to a graphic realization of the method of dynamic programming. Its concept was demonstrated by the examples of the partition and knapsack problems. The proposed method was compared with the existing algorithms to solve these problems.
We formulate the optimal control problem for a class of nonlinear objects that can be represented as objects with linear structure and state-dependent coefficients. We assume that the system is subjected to uncontrollable bounded disturbances. The linear structure of the transformed nonlinear system and the quadratic quality functional let us, in the optimal control synthesis, to pass from Hamilton–Jacobi–Isaacs equations to a state-dependent Riccati Equation. Control of nonlinear uncertain object in the problem of moving along a given trajectory is considered using the theory of differential games. We also give an example that illustrates how theoretical results of this work can be used.