Complexity of the word problem for commutative semigroups of fixed dimension

Summary In this paper we investigate the computational complexity of the word problem for commutative semigroups of fixed dimension. It is shown that for commutative semigroups of dimension k, k 6, the word problem is complete for symmetric linear space, providing another complete problem for this symmetric complexity class. We also show that in the case of one generator, the word problem is solvable in polynomial time.     

Finite-state dimension and real arithmetic

We use entropy rates and Schur concavity to prove that, for every integer k ⩾ 2, every nonzero rational number q, and every real number α, the base-k expansions of α, q + α, and qα all have the same finite-state dimension and the same finite-state strong dimension. This extends, and gives a new proof of, Wall’s 1949 theorem stating that the sum or product of a nonzero rational number and a Borel normal number is always Borel normal.     

Complexity of some arithmetic problems for binary polynomials

We study various combinatorial complexity measures of Boolean functions related to some natural arithmetic problems about binary polynomials, that is, polynomials over . In particular, we consider the Boolean function deciding whether a given polynomial over is squarefree. We obtain an exponential lower bound on the size of a decision tree for this function, and derive an asymptotic formula, having a linear main term, for its average sensitivity. This allows us to estimate other complexity characteristics such as the formula size, the average decision tree depth and the degrees of exact and approximative polynomial representations of this function. Finally, using a different method, we show that testing squarefreeness and irreducibility of polynomials over cannot be done in for any odd prime p. Similar results are obtained for deciding coprimality of two polynomials over as well.     

维度不变的格基代理广播加密方案*

为解决量子环境下广播加密的安全和效率问题,本文结合Shweta等人提出的维度不变的格基代理生成算法,设计出一种格上基于身份的广播加密方案。该方案采用“父格”与“子格”的结构关系来表示系统主私钥与合法用户私钥的对应关系,合法用户可以利用自己的私钥解密广播信息。不同于以往方案,该算法利用系统主私钥生成合法用户私钥的时候,不会增加用户私钥的维度。在随机预言机模型下证明该方案是适应性安全的,其安全性规约到错误学习（LWE）问题。     

Linear-time algorithms for problems on planar graphs with fixed disk dimension

The disk dimension of a planar graph G is the least number k for which G embeds in the plane minus k open disks, with every vertex on the boundary of some disk. Useful properties of graphs with a given disk dimension are derived, leading to an algorithm to obtain an outerplanar subgraph of a graph with disk dimension k by removing at most 2k−2 vertices. This reduction is used to obtain linear-time exact and approximation algorithms on graphs with fixed disk dimension. In particular, a linear-time approximation algorithm is presented for the pathwidth problem.     

Complexity of dimension three and some related edge-covering characteristics of graphs

We study systems of inference rules for multivalued dependencies in database relations. For such systems we define a new notion of completeness in which the underlying universe of attributes is left undetermined, whereas the earlier studied concept of completeness refers to a fixed finite universe. We introduce a new inference rule, the subset rule, and using this rule we prove that a certain system is complete. Furthermore we clarify the role of the so-called complementation rule.     

Complexity results for an integrated single machine scheduling and outbound delivery problem with fixed sequence

In this paper, we consider an integrated production and outbound delivery scheduling problem. In particular, we address the situation in which the scheduling sequence and the delivery sequence are the same and predefined. A set of jobs are processed on a single machine, and finished jobs are delivered to the customers by a single capacitated vehicle. Each job has a processing time, and transportation times between customers are taken into account. Because the sequence is given, the problem consists in forming batches of jobs and our objective is to minimize the sum of the delivery times or general functions of the delivery times. The NP-hardness of the general problem is established, and a pseudopolynomial time dynamic programming algorithm is given. Some particular cases are treated, for which NP-hardness proofs and polynomial time algorithms are given. Finally, a fixed-parameter tractability result is given.     

Personalized quantifier by Bernstein polynomials combined with interpolation spline

A new form of personalized quantifier is developed in this paper, with which to investigate and formalize people's personalities or behavior intentions that have to be considered in increasingly complex situations. As we show in the article, the developed quantifier is realized by generalized Bernstein polynomials combined with interpolation spline, and finally expressed as a sequence of piecewise nonlinear polynomials with an adjustable degree. It is characterized by many excellent properties exemplified by such terms as sufficient smoothness, shape‐preserving interpolation, and a high rate of convergence. In particular, the consistency of the ordered weighted averaging (OWA) aggregation under the guidance of the developed quantifier is addressed and proved. This actually provides a sound theoretical basis for practical use. We also experimentally show that the developed quantifier significantly outperforms, in all respects of geometrical characteristics, the other ones presented in previous work, whether from a viewpoint of global approximation of functions or local one. As such, the developed quantifier could be considered as an effective analytical tool for decision making under uncertainty in which different personality traits have to be taken into account.     

On the properties of equidifferent RIM quantifier with generating function

Comparing the large number of research papers on the ordered weighted averaging (OWA) operator, the researches on relative quantifier are relatively rare so far. In the present paper, based on the quantifier guided aggregation method with OWA operator which was proposed by Yager [“Quantifier guided aggregation using OWA operators”, Int. J. Intell. Syst., 11, pp. 49–73, 1996], a generating function representation method for regular increasing monotone (RIM) quantifiers is proposed. We extend the the properties of OWA operator to the RIM quantifier which is represented with a monotone function instead of the OWA weighting vector. A class of parameterized equidifferent RIM quantifier which has minimum variance generating function is proposed and its properties are also analyzed. The equidifferent RIM quantifier is consistent with its orness level for any aggregated elements, which can be used to represent the decision maker's preference.     

Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: Complexity,properties and formulations

We consider a variant of the Min-Degree Constrained Minimum Spanning Tree Problem where the central and terminal nodes are fixed a priori. We prove that the optimization problem is NP-Hard even for complete graphs and the feasibility problem is NP-Complete even if there is an edge between each central and each terminal in the input graph. Actually, this complexity result still holds when the minimum degree of each central node is restricted to be a same value d ≥ 2. We derive necessary and sufficient conditions for feasibility. We present several integer linear programming formulations – based on known formulations for the minimum spanning tree problem – along with a theoretical comparison among the lower bounds provided by their linear relaxations. We propose three Lagrangian heuristics. Computational experiments compare the performances of the heuristics and the formulations.     

Some quantifier functions from weighting functions with constant value of orness.

The quantifier-guided aggregation is used for aggregating the multiple-criteria input. Therefore, the selection of appropriate quantifiers is crucial in multicriteria aggregation since the weights for the aggregation are generated from the selected quantifier. Since Yager proposed a method for obtaining the ordered weighted averaging (OWA) vector via the three relative quantifiers used for the quantifier-guided aggregation, limited efforts have been devoted to developing new quantifiers that are suitable for use in multicriteria aggregation. In this correspondence, we propose some new quantifier functions that are based on the weighting functions characterized by showing a constant value of orness independent of the number of criteria aggregated. The proposed regular increasing monotone and regular decreasing monotone quantifiers produce the same orness as the weighting functions from which each quantifier function originates. Further, the quantifier orness rapidly converges into the value of orness of the weighting functions having a constant value of orness. This result indicates that a quantifier-guided OWA aggregation will result in a similar aggregate in case the number of criteria is not too small.     

一种处理障碍约束的聚类算法

根据障碍约束空间聚类问题的特点,利用图论的相关知识,提出了一种分阶段的基于图的聚类的算法。首先,通过最小生成树聚类算法,在不考虑障碍约束的情况下对空间对象进行聚类;然后,引入障碍物对上一步的聚类结果进行分割;最后,根据被障碍物分割后形成的各个类之间的障碍距离,将距离较近的两个类合并,形成最终的聚类结果。最后通过实验验证了算法的效果,而且输入参数少,时间复杂度低。     

A quantifier elimination for the theory of p-adic numbers

This paper presents a detailed analysis of a quantifier elimination algorithm for the first order theory of p-adic numbers based on a p-adic analogue of the cylindrical algebraic decomposition. It is believed that this method should lead to an elementary upper bound for the theory. The present paper gives strong arguments against this conjecture and offers a basis for further speculation. Received: 10 March 1996     

Hierarchical matrix arithmetic with accumulated updates

Hierarchical matrices can be used to construct efficient preconditioners for partial differential and integral equations by taking advantage of low-rank structures in triangular factorizations and inverses of the corresponding stiffness matrices. The setup phase of these preconditioners relies heavily on low-rank updates that are responsible for a large part of the algorithm’s total run-time, particularly for matrices resulting from three-dimensional problems. This article presents a new algorithm that significantly reduces the number of low-rank updates and can shorten the setup time by 50% or more.

     

Ensemble of surrogates with recursive arithmetic average

Surrogate models are often used to replace expensive simulations of engineering problems. The common approach is to construct a series of metamodels based on a training set, and then, from these surrogates, pick out the best one with the highest accuracy as an approximation of the computationally intensive simulation. However, because the choice of approximate model depends on design of experiments (DOEs), the traditional strategy thus increases the risk of adopting an inappropriate model. Furthermore, in the design of complex product system, because of its feature of one-of-a-kind production, acquiring more samples is very expensive and intensively time-consuming, and sometimes even impossible. Therefore, in order to save sampling cost, it is a reasonable strategy to take full advantage of all the stand-alone surrogates and then combine them into an ensemble model. Ensemble technique is an effective way to make up for the shortfalls of traditional strategy. Motivated by the previous research on ensemble of surrogates, a new technique for constructing of a more accurate ensemble of surrogates is proposed in this paper. The weights are obtained using a recursive process, in which the values of these weights are updated in each iteration until the last ensemble achieves a desirable prediction accuracy. This technique has been evaluated using five benchmark problems and one reality problem. The results show that the proposed ensemble of surrogates with recursive arithmetic average provides more ideal prediction accuracy than the stand-alone surrogates and for most problems even exceeds the previously presented ensemble techniques. Finally, we should point out that the advantages of combination over selection are still difficult to illuminate. We are still using an “insurance policy” mode rather than offering significant improvements.     

The quantifier structure of sentences that characterize nondeterministic time complexity

For every nondeterministic Turing machineM of time complexityT(n), there is a second-order sentence of a very restricted form, whose set of finite models encodes the set of strings recognized byM. Specifically, has a relational symbol which is interpreted as addition restricted to finite segments of the natural numbers, and a prefix consisting of existentially quantified unary second-order variables followed by a universal-existential first-order part. Here, every input stringx is encoded by a model of sizeT(|x|). Using a closely related encoding of strings as models where the size of the model is the length of the string, a consequence is that ifT(n)=n ^d, then there is a sentence with a similar prefix but whose second-order variables ared-ary and whose finite models encode the strings accepted byM. Potential applications to low-level complexity are discussed.     

Out of order quantifier elimination for Standard Quantified Linear Programs

In this paper, we present an out of order quantifier elimination algorithm for a class of Quantified Linear Programs (QLPs) called Standard Quantified Linear Programs (SQLPs). QLPs in general and SQLPs in particular are extremely useful constraint logic programming structures that find wide applicability in the modeling of real-time schedulability specifications; see Subramani [Subramani, K., 2005a. A comprehensive framework for specifying clairvoyance, constraints and periodicity in real-time scheduling. The Computer Journal 48 (3), 259–272]. Consequently any algorithmic advance in their solution has a strong practical impact. Prior to this work, the only known approaches to the solution of QLPs involved sequential variable elimination; see Subramani [Subramani, K., 2003b. An analysis of quantified linear programs. In: Calude, C.S. et al. (Eds.), Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science. DMTCS. In: Lecture Notes in Computer Science, vol. 2731. Springer-Verlag, pp. 265–277]. In the sequential approach, the innermost quantified variable is eliminated first, followed by the variable which then becomes the innermost quantified variable and so on, until we are left with a single variable from which the satisfiability of the original formula is easily deduced. This approach is applicable in both discrete and continuous domains; however, it is to be noted that the logic demanding the sequential approach requires that the variables are discrete-valued. To the best of our knowledge, the necessity for sequential elimination over continuous-valued variables has not been investigated in the literature. The techniques used in the development of our elimination algorithm may find applications in domains such as classical logic and finite model theory. The final aspect of our research concerns the structure-preserving nature of the algorithm that we introduce here; in general, it is not known whether discrete domains admit such elimination procedures.