The Distribution of Irreducible Polynomials in Fq[t]

The purpose of this article is to get effective information about the following two problems: (1) Making a polynomial irreducible by changing coefficients of lower degree terms. (2) Existence of irreducibles of low degree in a given arithmetic progression in polynomial ring over finite field.     

Number of irreducible polynomials and pairs of relatively prime polynomials in several variables over finite fields

We discuss several enumerative results for irreducible polynomials of a given degree and pairs of relatively prime polynomials of given degrees in several variables over finite fields. Two notions of degree, the total degree and the vector degree, are considered. We show that the number of irreducibles can be computed recursively by degree and that the number of relatively prime pairs can be expressed in terms of the number of irreducibles. We also obtain asymptotic formulas for the number of irreducibles and the number of relatively prime pairs. The asymptotic formulas for the number of irreducibles generalize and improve several previous results by Carlitz, Cohen and Bodin.     

The uniqueness of the core

Simple proofs are given for two theorems of Duffus and Rival: If a finite poset is dismantled by irreducibles as much as possible, the subposet one finally obtains is unique up to isomorphism. If one dismantles by doubly irreducibles, the subposet is unique.     

Some decision and counting problems of the Duquenne-Guigues basis of implications

Implications of a formal context obey Armstrong rules, which allows one to define a minimal (in the number of implications) implication basis, called Duquenne-Guigues basis or stem base in the literature. In this paper we show how implications are reduced to functional dependencies and prove that the problem of determining the size of the stem base is a #P-complete problem.     

Stochastic Enumeration Method for Counting NP-Hard Problems

We present a new generic sequential importance sampling algorithm, called stochastic enumeration (SE) for counting #P-complete problems, such as the number of satisfiability assignments and the number of perfect matchings (permanent). We show that SE presents a natural generalization of the classic one-step-look-ahead algorithm in the sense that it: Runs in parallel multiple trajectories instead of a single one; Employs a polynomial time decision making oracle, which can be viewed as an n-step-look-ahead algorithm, where n is the size of the problem. Our simulation studies indicate good performance of SE as compared with the well-known splitting and SampleSearch methods.     

Order Extensions and the Fixed Point Property

The purpose of this paper is to investigate how the fixed point property and its negation behave when a covering relation is added to the order. We prove that every finite ordered set which is not totally ordered and which is dismantlable by retractables, respectively by irreducibles, has an upper cover (in its extension lattice) which is also dismantlable by retractables, respectively by irreducibles. We also provide examples of finite ordered sets having the fixed point property so that none of their upper covers has the fixed point property. Part of this work was done while the author was visiting Brandon University. The author thanks M. Roddy for his hospitality and financial support.     

Counting linear extensions

We survey the problem of counting the number of linear extensions of a partially ordered set. We show that this problem is #P-complete, settling a long-standing open question. This result is contrasted with recent work giving randomized polynomial-time algorithms for estimating the number of linear extensions.One consequence of our main result is that computing the volume of a rational polyhedron is strongly #P-hard. We also show that the closely related problems of determining the average height of an element x of a give poset, and of determining the probability that x lies below y in a random linear extension, are #P-complete.Research carried out while this author was visiting Bellcore under the auspices of DIMACS.     

Complexity issues on bounded restrictive H-coloring

We consider a bounded version of the restrictive and the restrictive list H-coloring problem in which the number of pre-images of certain vertices of H is taken as parameter. We consider the decision and the counting versions, as well as, further variations of those problems. We provide complexity results identifying the cases when the problems are NP-complete or #P-complete or polynomial time solvable. We conclude stating some open problems.     

Selection of Capacity Expansion Projects

The problem of determining a project selection schedule and a production-distribution-inventory schedule for each of a number of plants so as to meet the demands of multiregional markets at minimum discounted total cost during a discrete finite planning horizon is considered. We include the possibility of using inventory and/or imports to delay the expansion decision at each producing region in a transportation network. Through a problem reduction algorithm, the Lagrangean relaxation problem strengthened by the addition of a surrogate constraint becomes a 0–1 mixed integer knapsack problem. Its optimal solution, given a set of Lagrangean multipliers, can be obtained by solving at most two generally smaller 0–1 pure integer knapsack problems. The bound is usually very tight. At each iteration of the subgradient method, we generate a primal feasible solution from the Lagrangean solution. The computational results indicate that the procedure is effective in solving large problems to within acceptable error tolerances.     

A provably convergent heuristic for stochastic bicriteria integer programming

We propose a general-purpose algorithm APS (Adaptive Pareto-Sampling) for determining the set of Pareto-optimal solutions of bicriteria combinatorial optimization (CO) problems under uncertainty, where the objective functions are expectations of random variables depending on a decision from a finite feasible set. APS is iterative and population-based and combines random sampling with the solution of corresponding deterministic bicriteria CO problem instances. Special attention is given to the case where the corresponding deterministic bicriteria CO problem can be formulated as a bicriteria integer linear program (ILP). In this case, well-known solution techniques such as the algorithm by Chalmet et al. can be applied for solving the deterministic subproblem. If the execution of APS is terminated after a given number of iterations, only an approximate solution is obtained in general, such that APS must be considered a metaheuristic. Nevertheless, a strict mathematical result is shown that ensures, under rather mild conditions, convergence of the current solution set to the set of Pareto-optimal solutions. A modification replacing or supporting the bicriteria ILP solver by some metaheuristic for multicriteria CO problems is discussed. As an illustration, we outline the application of the method to stochastic bicriteria knapsack problems by specializing the general framework to this particular case and by providing computational examples.     

Methodology for the invariant estimation of a continuous distribution function

Consider both the calssical and some more general invariant decision problems of estimating a continuous distribution function, with the loss function {ie503-1} and a sample of sizen fromF. It is proved that any nonrandomized estimator can be approximated in Lebesgue measure by the more general invariant estimators. Some methods for investigating the finite sample problem are discussed. As an application, a proof that the best invariant estimator is minimax when the sample size is 1 is given.     

The counting complexity of a simple scheduling problem

Let T be a set of tasks. Each task has a non-negative processing time and a deadline. The problem of determining whether or not there is a schedule of the tasks in T such that a single machine can finish processing each of them before its deadline is polynomially solvable. We prove that counting the number of schedules satisfying this condition is #P-complete.     

基本概念格的数据扩展及相容性判定问题

数据分析在计算机数据处理中占有重要地位.概念格理论是数据分析有力工具,本文以概念格为工具,讨论数据扩展而引起的相容性问题.主要是将数据作为概念格中的对象,在给定数据基本集并假设数据特征一定的条件下,考虑数据扩展相容性问题,解决了数据扩展的相容性判定问题并给出了相应的判定定理.目的是使在特征一定的情况下,数据对象达到最大化.     

Reductions in Computational Complexity Using Clifford Algebras

A number of combinatorial problems are treated using properties of abelian null-square-generated and idempotent-generated subalgebras of Clifford algebras. For example, the problem of deciding whether or not a graph contains a Hamiltonian cycle is known to be NP-complete. By considering entries of Λ^k, where Λ is an appropriate nilpotent adjacency matrix, the k-cycles in any finite graph are recovered. Within the algebra context (i.e., considering the number of multiplications performed within the algebra), these problems are reduced to matrix multiplication, which is in complexity class P. The Hamiltonian cycle problem is one of many problems moved from classes NP-complete and #P-complete to class P in this context. Other problems considered include the set covering problem, counting the edge-disjoint cycle decompositions of a finite graph, computing the permanent of an arbitrary matrix, computing the girth and circumference of a graph, and finding the longest path in a graph.     

The effectiveness of finite improvement algorithms for finding global optima

This paper investigates the effectiveness of using finite improvement algorithms for solving decision, search, and optimization problems. Finite improvement algorithms operate in a finite number of iterations, each taking a polynomial amount of work, where strict improvement is required from iteration to iteration. The hardware, software, and way of measuring complexity found in the polynomial setting are modified to identify the concept of repetition and define the new classes of decision problems,FI andNFI. A firstNFI-complete problem is given using the idea ofFI-transformations. Results relating these new classes toP, NP, andNP-complete are given. It is shown that if an optimization problem in a new classPGS isNP-hard, thenNP=co-NP. TwoPGS problems are given for which no polynomial algorithms are known to exist.     

The fuzzy decision problem: An approach to the problem of testing statistical hypotheses with fuzzy information

This paper is devoted to the problems of testing statistical hypotheses about an experiment, when the available information from its sampling is `vague'. When the information supplied by the experimental sampling is exact, the problems of testing statistical hypotheses about the experiment can be regarded as a particular statistical decision problem. In addition, decision procedures may be used in problems of testing hypotheses.In a similar manner, the problem of testing statistical hypotheses about an experiment when the available sample information is vague, is approached in this paper as a particular fuzzy decision problem (as defined by Tanaka, Okuda and Asai). This approach assumes that the previous information about the experiment can be expressed by means of certain conditional probabilistic information, whereas the present information about it can be expressed by means of fuzzy information. The preceding framework allows us to extend the notion of risk function and some nonfuzzy decision procedures to the fuzzy case, and particularize them to the problem of testing.Finally, several illustrative examples are presented.     

多阶段应急决策的方案链选择方法

针对多阶段不同情景下多指标多任务的应急决策问题,提出了一种方案链选择方法。在该方法中,首先给出了决策方案链的概念,并对多阶段多指标多任务的应急决策问题进行了描述;然后根据相邻阶段的子方案之间的相容性,构建了相容性关系矩阵;进一步地,在考虑相邻阶段子方案之间相容性的情形下,以各阶段的子方案的综合评价值最大为目标,建立了应急决策的方案链选择的优化模型。通过求解模型,得到应急决策的最优方案链。最后,通过一个算例说明了该方法的可行性和有效性。     

A Bilevel Stochastic Programming Problem with Random Parameters in the Follower’s Objective Function

Under study is a bilevel stochastic linear programming problem with quantile criterion. Bilevel programming problems can be considered as formalization of the process of interaction between two parties. The first party is a Leader making a decision first; the second is a Follower making a decision knowing the Leader’s strategy and the realization of the random parameters. It is assumed that the Follower’s problem is linear if the realization of the random parameters and the Leader’s strategy are given. The aim of the Leader is the minimization of the quantile function of a loss function that depends on his own strategy and the optimal Follower’s strategy. It is shown that the Follower’s problem has a unique solution with probability 1 if the distribution of the random parameters is absolutely continuous. The lower-semicontinuity of the loss function is proved and some conditions are obtained of the solvability of the problem under consideration. Some example shows that the continuity of the quantile function cannot be provided. The sample average approximation of the problem is formulated. The conditions are given to provide that, as the sample size increases, the sample average approximation converges to the original problem with respect to the strategy and the objective value. It is shown that the convergence conditions hold for almost all values of the reliability level. A model example is given of determining the tax rate, and the numerical experiments are executed for this example.     

Parallel multi-frontal solver for p adaptive finite element modeling of multi-physics computational problems

The paper presents a parallel direct solver for multi-physics problems. The solver is dedicated for solving problems resulting from adaptive finite element method computations. The concept of finite element is actually replaced by the concept of the node. The computational mesh consists of several nodes, related to element vertices, edges, faces and interiors. The ordering of unknowns in the solver is performed on the level of nodes. The concept of the node can be efficiently utilized in order to recognize unknowns that can be eliminated at a given node of the elimination tree. The solver is tested on the exemplary three-dimensional multi-physics problem involving the computations of the linear acoustics coupled with linear elasticity. The three-dimensional tetrahedral mesh generation and the solver algorithm are modeled by using graph grammar formalism. The execution time and the memory usage of the solver are compared with the MUMPS solver.     

Embedding Ordered Sets into Distributive Lattices

This paper investigates the class of ordered sets that are embeddable into a distributive lattice in such a way that all existing finite meets and joins are preserved. The main result is that the following decision problem is NP-complete: Given a finite ordered set, is it embeddable into a distributive lattice with preservation of existing meets and joins? The NP-hardness of the problem is proved by polynomial reduction of the classical 3SAT decision problem into it, and the NP-completeness by presenting a suitable NP-algorithm.