Two optimization problems in linear regression with interval data

We consider a linear regression model where neither regressors nor the dependent variable is observable; only intervals are available which are assumed to cover the unobservable data points. Our task is to compute tight bounds for the residual errors of minimum-norm estimators of regression parameters with various norms (corresponding to least absolute deviations (LAD), ordinary least squares (OLS), generalized least squares (GLS) and Chebyshev approximation). The computation of the error bounds can be formulated as a pair of max–min and min–min box-constrained optimization problems. We give a detailed complexity-theoretic analysis of them. First, we prove that they are NP-hard in general. Then, further analysis explains the sources of NP-hardness. We investigate three restrictions when the problem is solvable in polynomial time: the case when the parameter space is known apriori to be restricted into a particular orthant, the case when the regression model has a fixed number of regression parameters, and the case when only the dependent variable is observed with errors. We propose a method, called orthant decomposition of the parameter space, which is the main tool for obtaining polynomial-time computability results.     

伽罗瓦环上的一类No序列的构造

近年来,伽罗瓦环上的序列理论成为人们研究的热点问题.有限域上的No序列是一类伪随机序列,它在序列密码中占具十分重要的角色.本文利用伽罗瓦环上的置换,构造了伽罗瓦环Z_(p~e)上的一类新的No序列,并且研究了其线性复杂度.研究的结果表明此类No序列具有相当大的线性复杂度.     

Computational complexity of hybrid interval temporal logics

Interval logics are very expressive temporal formalisms, but reasoning with them is often undecidable or has high computational complexity. As a result, a vast number of approaches limiting their expressive power—in order to obtain better computational behaviour—have been introduced. Unfortunately, due to such restrictions, interval logics often lose referentiality, that is, the capacity to refer to specific time intervals, which is crucial for temporal representation and reasoning. The computational price that needs to be paid in order to regain referentiality is not well studied and our research aims to fill this gap. In particular we study the main interval temporal logic, called the Halpern-Shoham logic, and its low complexity modifications. To regain referentiality in these modifications, we extend the language with the hybrid machinery—nominals and satisfaction operators—and classify the obtained logics according to their computational complexity. We show that such a hybridisation often makes tractable logics intractable but not undecidable. This allows us to construct hybrid interval temporal logics which are referential as well as maintain a good compromise between expressiveness and complexity; it makes them valuable formalisms for temporal knowledge representation. We also introduce a class of models which, due to a specific interplay between the interpretation of modal operators and a structure of time, makes reasoning in interval logics computationally hard even in the absence of the hybrid machinery.     

A historical note on the complexity of scheduling problems

In 1972 E.M. Livshits and V.I. Rublinetsky published a paper in Russian, in which they presented linear-time reductions of the partition problem to a number of scheduling problems. Unaware of complexity theory, they argued that, since partition is not known to have a simple algorithm, one cannot expect to find simple algorithms for these scheduling problems either. Their work did not go completely unnoticed, but it received little recognition. We describe the approach and review the results.     

Infinite family of transmission irregular trees of even order

Distance between two vertices is the number of edges in a shortest path connecting them in a connected graph $G$. The transmission of a vertex $v$ is the sum of distances from $v$ to all the other vertices of $G$. If transmissions of all vertices are mutually distinct, then $G$ is a transmission irregular graph. It is known that almost no graphs are transmission irregular. Infinite families of transmission irregular trees of odd order were presented in Alizadeh and Klav?ar (2018). The following problem was posed in Alizadeh and Klav?ar (2018): do there exist infinite families of transmission irregular trees of even order? In this article, such a family is constructed.     

Consecutive Supramolecular Polymerization of a Rylene-Based Twistacene

The synthesis and self-assembling features of twistacene 1 are reported. The supramolecular polymerization of 1 displays a consecutive pathway to afford slipped ( AggI ) and rotationally displaced ( AggII ) aggregates conditioned by the formation of intramolecularly H-bonded pseudocycles. In methylcyclohexane, both AggI and AggII are highly stable and the interconversion of the kinetically controlled AggI into the thermodynamically controlled AggII takes several weeks to occur. The utilization of toluene as solvent changes the energetic level for both aggregates and favors a faster conversion of AggI into AggII within a period of minutes. This conversion can be accelerated by the addition of seeds. Furthermore, concentration dependent kinetic studies demonstrate the consecutive character of the supramolecular polymerization of 1 .     

A logarithmic complexity floating frame of reference formulation with interpolating splines for articulated multi-flexible-body dynamics

An interpolating spline-based approach is presented for modeling multi-flexible-body systems in the divide-and-conquer (DCA) scheme. This algorithm uses the floating frame of reference formulation and piecewise spline functions to construct and solve the non-linear equations of motion of the multi-flexible-body system undergoing large rotations and translations. The new approach is compared with the flexible DCA (FDCA) that uses the assumed modes method [1]. The FDCA, in many cases, must resort to sub-structuring to accurately model the deformation of the system. We demonstrate, through numerical examples, that the interpolating spline-based approach is comparable in accuracy and superior in efficiency to the FDCA. The present approach is appropriate for modeling flexible mechanisms with thin 1D bodies undergoing large rotations and translations, including those with irregular shapes. As such, the present approach extends the current capability of the DCA to model deformable systems. The algorithm retains the theoretical logarithmic complexity inherent in the DCA when implemented in parallel.     

A Structural Entropy Measurement Principle of Propositional Formulas in Conjunctive Normal Form

The satisfiability (SAT) problem is a core problem in computer science. Existing studies have shown that most industrial SAT instances can be effectively solved by modern SAT solvers while random SAT instances cannot. It is believed that the structural characteristics of different SAT formula classes are the reasons behind this difference. In this paper, we study the structural properties of propositional formulas in conjunctive normal form (CNF) by the principle of structural entropy of formulas. First, we used structural entropy to measure the complex structure of a formula and found that the difficulty solving the formula is related to the structural entropy of the formula. The smaller the compressing information of a formula, the more difficult it is to solve the formula. Secondly, we proposed a λ-approximation strategy to approximate the structural entropy of large formulas. The experimental results showed that the proposed strategy can effectively approximate the structural entropy of the original formula and that the approximation ratio is more than 92%. Finally, we analyzed the structural properties of a formula in the solution process and found that a local search solver tends to select variables in different communities to perform the next round of searches during a search and that the structural entropy of a variable affects the probability of the variable being flipped. By using these conclusions, we also proposed an initial candidate solution generation strategy for a local search for SAT, and the experimental results showed that this strategy effectively improves the performance of the solvers CCAsat and Sparrow2011 when incorporated into these two solvers.