Complexity of vector optimization problems on graphs

The paper is dedicated to the computation complexity of multi-objective optimization problems on graphs. The classes of multi-objective problems with polynomial complexity or being polynomially reduced to be NP-hard are marked out. The unsolvability of a series of combinatorial multi-objective problems has been set up by means of linear convolution algorithm. The sufficient conditions under which these algorithms are statistically efficient have also been obtained.     

Parallel algebraic reductions among numerical problems

In this note we consider, for a number of linear algebra problems, an environment allowing approximate computations. Within this framework we show that the relative complexity of these problems should be studied according to a strict notion of reducibility, which corresponds to the well-known many-one reducibility of combinatorial complexity.     

Solvable classes of discrete dynamic programming

As finite state models to represent a discrete optimization problem given in the form of an r-ddp (recursive discrete decision process), three subclasses of r-msdp (recursive monotone sequential decision process) are introduced in this paper. They all have a feature that the functional equations of dynamic programming hold and there exists an algorithm (in the sense of the theory of computation) to obtain the set of optimal policies. (In this sense, we may call them solvable classes of discrete dynamic programming.) Besides the algorithms for obtaining optimal policies, two types of representations are extensively studied for each class of r-msdp's. Other related decision problems are also discussed. It turns out that some of them are solvable while the rest of them are unsolvable.     

Automated classification and recognition information systems

Operating principles, situation classes, and problem formalization are examined in automated informational classification (and recognition) systems (ICS and IRS). The structure of the mentioned systems is proposed, problem criteria in the IRS are extracted, on whose basis classes of solvable problems are determined. The situation classes occurring during user interaction with the IRS are represented by tables.Translated from Dinamicheskie Sistemy, No. 4, pp. 96–101, 1985.     

Spectral Residues of Second-order Differential Equations: A New Method for Summation Identities and Inversion Formulas

This article deals with differential equations with spectral parameter from the point of view of formal power series.The treatment does not make use of the notion of eigenvalue, but introduces a new idea: the spectral residue.
The article focuses on second-order, self-adjoint problems. In such a setting, every potential function determines a sequence of spectral residues. This correspondence is invertible and gives rise to a combinatorial inversion formula. Other interesting combinatorial consequences are obtained by considering spectral residues of exactly solvable potentials of one-dimensional quantum mechanics.
It is also shown that the Darboux transformation of one-dimensional potentials corresponds to a simple negation of the corresponding spectral residues. This fact leads to another combinatorial inversion formula. Finally, there is a brief discussion of applications. The topics considered are enumeration problems and integrable systems.     

Unsolvable algorithmic problems for semigroups,groups, and rings

A survey of the subject outlined in the heading (with many proof s sketched) is given. A special focus is on the original proofs of the unsolvability theorems of Markov, Post, and Novikov for word problems in semigroups and groups. A method of Shirshov is described, which has led to proof of the main unsolvability theorems for Lie algebras.Translated from Itogi Nauki I Tekhniki, Seriya Algebra, Topologiya, Geometriya, Vol. 25, pp. 3–66, 1987.The Russian names in this survey are given according to standard transliteration. Some Russian authors, however, are also known in the Western literature in a different spelling. The corresponding equivalents are given below, in alphabetical order:     

Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes

An identifying code is a subset of vertices of a graph with the property that each vertex is uniquely determined (identified) by its nonempty neighbourhood within the identifying code. When only vertices out of the code are asked to be identified, we get the related concept of a locating-dominating set. These notions are closely related to a number of similar and well-studied concepts such as the one of a test cover. In this paper, we study the decision problems Identifying Code and Locating-Dominating Set (which consist in deciding whether a given graph admits an identifying code or a locating-dominating set, respectively, with a given size) and their minimization variants Minimum Identifying Code and Minimum Locating-Dominating Set. These problems are known to be NP-hard, even when the input graph belongs to a number of specific graph classes such as planar bipartite graphs. Moreover, it is known that they are approximable within a logarithmic factor, but hard to approximate within any sub-logarithmic factor. We extend the latter result to the case where the input graph is bipartite, split or co-bipartite: both problems remain hard in these cases. Among other results, we also show that for bipartite graphs of bounded maximum degree (at least 3), the two problems are hard to approximate within some constant factor, a question which was open. We summarize all known results in the area, and we compare them to the ones for the related problem Dominating Set. In particular, our work exhibits important graph classes for which Dominating Set is efficiently solvable, but Identifying Code and Locating-Dominating Set are hard (whereas in all previous works, their complexity was the same). We also introduce graph classes for which the converse holds, and for which the complexities of Identifying Code and Locating-Dominating Set differ.     

On a Conjecture of Kleene and Post

A proof is given that 0 ′ (the argest Turing degree containing a computably enumerable set) is definable in the structure of the degrees of unsolvability. This answers a long‐standing question of Kleene and Post, and has a number of corollaries including the definability of the jump operator.     

On the relation between complexity and uncertainty

In practical problem situations data are usually inherently unreliable. A mathematical representation of uncertainty leads to stochastic optimization problems. In this paper the complexity of stochastic combinatorial optimization problems is discussed. Surprisingly, certain stochastic versions of NP-hard determinstic combinatorial problems appear to be solvable in polynomial time.     

Right-angled Artin groups and a generalized isomorphism problem for finitely generated subgroups of mapping class groups

Consider the mapping class group Mod _g,p of a surface ?? _g,p of genus g with p punctures, and a finite collection {f₁, . . . , f_k} of mapping classes, each of which is either a Dehn twist about a simple closed curve or a pseudo-Anosov homeomorphism supported on a connected subsurface. In this paper we prove that for all sufficiently large N, the mapping classes ${\{f_1^N,\ldots,f_k^N\}}$ generate a right-angled Artin group. The right-angled Artin group which they generate can be determined from the combinatorial topology of the mapping classes themselves. When {f₁, . . . , f_k} are arbitrary mapping classes, we show that sufficiently large powers of these mapping classes generate a group which embeds in a right-angled Artin group in a controlled way. We establish some analogous results for real and complex hyperbolic manifolds. We also discuss the unsolvability of the isomorphism problem for finitely generated subgroups of Mod _g,p , and recover the fact that the isomorphism problem for right-angled Artin groups is solvable. We thus characterize the isomorphism type of many naturally occurring subgroups of Mod _g,p .     

Image normalization of Wiener-Hopf operators and boundary-transmission value problems for a junction of two half-planes

The present paper deals with an application of the image normalization technique for certain classes of Wiener-Hopf operators (WHOs) associated to ill-posed boundary-transmission value problems. We briefly describe the method of normalization and then apply it to boundary-transmission value problems issued from diffraction problems for a junction of two half-planes, which are relevant in mathematical physics applications. For each boundary-transmission value problem, we analyze the conditions under which the associated operator and the equivalent WHO are not normally solvable, and define the corresponding image normalized operators.     

Forbidden substructures and combinatorial dichotomies: WQO and universality

We discuss two combinatorial problems concerning classes of finite or countable structures of combinatorial type. We consider classes determined by a finite set of finite constraints (forbidden substructures). Questions about such classes of structures are naturally viewed as algorithmic decision problems, taking the finite set of constraints as the input. While the two problems we consider have been studied in a number of natural contexts, it remains far from clear whether they are decidable in their general form. This broad question leads to a number of more concrete problems. We discuss twelve open problems of varying levels of concreteness, and we point to the “Hairy Ball Problem” as a particularly concrete problem, which we give first in direct model theoretic terms, and then decoded as an explicit graph theoretic problem.     

The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes

The exact weighted independent set (EWIS) problem consists in determining whether a given vertex-weighted graph contains an independent set of given weight. This problem is a generalization of two well-known problems, the NP-complete subset sum problem and the strongly NP-hard maximum weight independent set (MWIS) problem. Since the MWIS problem is polynomially solvable for some special graph classes, it is interesting to determine the complexity of this more general EWIS problem for such graph classes.We focus on the class of perfect graphs, which is one of the most general graph classes where the MWIS problem can be solved in polynomial time. It turns out that for certain subclasses of perfect graphs, the EWIS problem is solvable in pseudo-polynomial time, while on some others it remains strongly NP-complete. In particular, we show that the EWIS problem is strongly NP-complete for bipartite graphs of maximum degree three, but solvable in pseudo-polynomial time for cographs, interval graphs and chordal graphs, as well as for some other related graph classes.     

The Unsolvability of Inverse Algebraic Eigenvalue Problems Almost Everywhere

This paper revises the definition for the unsolvability of inverse algebraic eigenvalue problems almost everywhere (a.e.) given by Shapiro [5], and gives some sufficient and necessary conditions such that the inverse algebraic eigenvalue problems are unsolvable a.e.     

Min–max and min–max (relative) regret approaches to representatives selection problem

The following optimization problem is studied. There are several sets of integer positive numbers whose values are uncertain. The problem is to select one representative of each set such that the sum of the selected numbers is minimum. The uncertainty is modeled by discrete and interval scenarios, and the min?Cmax and min?Cmax (relative) regret approaches are used for making a selection decision. The arising min?Cmax, min?Cmax regret and min?Cmax relative regret optimization problems are shown to be polynomially solvable for interval scenarios. For discrete scenarios, they are proved to be NP-hard in the strong sense if the number of scenarios is part of the input. If it is part of the problem type, then they are NP-hard in the ordinary sense, pseudo-polynomially solvable by a dynamic programming algorithm and possess an FPTAS. This study is motivated by the problem of selecting tools of minimum total cost in the design of a production line.     

Possibilistic bottleneck combinatorial optimization problems with ill-known weights

In this paper a general bottleneck combinatorial optimization problem with uncertain element weights modeled by fuzzy intervals is considered. A possibilistic formalization of the problem and solution concepts in this setting, which lead to compute robust solutions under fuzzy weights, are given. Some algorithms for finding a solution according to the introduced concepts and evaluating optimality of solutions and elements are provided. These algorithms are polynomial for bottleneck combinatorial optimization problems with uncertain element weights, if their deterministic counterparts are polynomially solvable.     

Estimation of the Absolute Error and Polynomial Solvability for a Classical <Emphasis Type="Italic">NP</Emphasis>-Hard Scheduling Problem

A method for finding an approximate solution for NP-hard scheduling problems is proposed. The example of the classical NP-hard in the strong sense problem of minimizing the maximum lateness of job processing with a single machine shows how a metric introduced on the instance space of the problem and polynomially solvable areas can be used to find an approximate solution with a guaranteed absolute error. The method is evaluated theoretically and experimentally and is compared with the ED-heuristic. Additionally, for the problem under consideration, we propose a numerical characteristic of polynomial unsolvability, namely, an upper bound for the guaranteed absolute error for each equivalence class of the instance space.     

A graph partition problem

ＡＧＲＡＰＨＰＡＲＴＩＴＩＯＮＰＲＯＢＬＥＭ￥ＬＩＵＴＡＮＰＥＩ（刘彦佩）（ＤｅｐａｒｆｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ,ＮｏｒｔｈｅｒｎＪｉａｏｔｏｎｙＵｎｉｖｅｒｓｉｔｙ,Ｂｅｉｊｉｎｇ１０００４４,Ｃｈｉｎａ）ＡＵＲＯＲＡＭＯＲＧＡＮＡ（Ｄｅ...     

THE UNSOLVABILITY OF GENERALIZED INVERSE EIGENVALUE PROBLEMS ALMOST EVERYWHERE

In this paper the unsolvability of generalized inverse eigenvalue problems almost everywhere is discussed.We first give the definitions for the unsolvability of generalized inverse eigenvalue problems almost everywhere.Then adopting the method used in [14],we present some sufficient conditions such that the generalized inverse eigenvalue problems are unsohable almost everywhere.