有理数域上二元多项式正定性的单点判定法

文中给出了一个用于判定有理数域上二元多项式正定性的算法,并利用Seidenberg代数曲线决定法证明了该算法的正确性.据此算法编制的Maple程序IsDefinite通过判定该多项式在平面上一个点处取值的符号就能够判定出该多项式是否正定.     

可满足性问题全部解的求解算法

SAT问题在人工智能、计算机基础理论研究和人工智能等领域有着广泛的应用,近年来,证明该问题的可满足性取得了巨大的成功,但在求出SAT问题的所有解方面还有待进一步研究。利用一个简单的变换,将可满足性（SAT）问题转化为多项式形式,然后根据命题逻辑的性质以及多项式的性质,得到一个求解出SAT问题所有解的算法。实验结果显示该算法是有效和可行的。     

NTRU中多项式的逆问题

在NTRU公钥密码体制中,一个多项式是否有逆多项式是一个很重要的问题.本文介绍了NTRU公钥密码体制,给出了NTRU中多项式是否有逆的判定定理,并对所提出的定理进行了相应的证明.最后我们用例子来说明怎样运用该判定定理,给出了求解多项式逆的算法.     

求解难可满足性问题的混合算法

提出了一个求解难可满足性问题的简单混合算法．拟人和禁忌表两个策略被给出．数值实验表明，对于一类公认比较难的可满足性问题，该算法胜过目前据认为是最好方法之一的NOVELTY算法．     

函数依赖集F有内部冲突的判定问题研究

在讨论数据库模式R(W，F)的无α环分解时，需要判定FD集F是否有内部冲突；在讨论无β，γ环的分解时也需要判定是否有内部冲突．为此，应当首先给出归并依赖集的二元组集合、闭包等概念；分别给出求解二元组集合及其闭包的多项式算法．在此基础上，讨论FD集F有内部冲突时的特征和相关条件，给出相应的有内部冲突的判定定理和算法，对算法进行了证明和分析．     

非对称选择网活性的一个多项式时间判定

活性判定是Petri网中一直没有完全解决的问题．针对非对称选择网的活性问题,利用结构分析理论,作了进一步的研究．首先,讨论和分析了活性判定的一般方法,然后利用S－不变,提出了非对称选择网活性判定的一个充分条件,并给出了相应的多项式算法．同时,对有界的非对称选择网的活性单调性问题进行了深入的研究,得到了一个简单的充分必要条件     

指数函数多项式的实根分离算法

针对超越函数多项式的实根分离问题，提出了一种指数函数多项式的区间分离算法exRoot，将非多项式型实函数的实根分离问题转化为多项式正负性判定问题进而对其求解。首先，利用泰勒替换法构造目标函数的多项式区间套；然后，将指数函数的求根问题转化为多项式在区间内正负性的判定问题；最后，给出综合算法，并且试探性地应用于实特征值线性系统的可达性判定问题。所提算法在Maple中实现，输出的结果可读，且高效易行。区别于HSOLVER和数值计算方法fsolve，exRoot回避了直接讨论根的存在性问题，理论上具有终止性和完备性，且可达到任意精度，应用于最优化问题时可避免数值解带来的系统误差。     

CP-nets的可满足性及一致性研究

CP-nets是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点,然而对于CP-nets的可满足性和一致性等相关性质的研究还很欠缺.既没有给出严格的定义,也没有探讨不同性质之间的联系,没有一个求可满足性序列的通用算法.从研究CP-nets的可满足性和一致性的关系着手,得出了任意结构二值CP-nets的可满足性判定算法及可满足性序列生成算法.首先通过构造CP-nets导出图及其性质的研究,得出CP-nets的可满足性及一致性的相关定理.再把不同性质结合起来分析,给出CP-nets可满足性等价于一致性的结论,从而利用拓扑排序的思想实现了任意结构二值CP-nets的可满足性序列的生成.强化和扩充了Boutilier所提出的一些概念,深化了CP-nets的基础理论研究.     

求解含非线性参数的QoS路由的启发式算法

具有非线性参数的QoS路由分为含有非线性约束条件的QoS路由和含有非线性优化目标的QoS路由两类，它们都是NP问题．提出了两种启发式算法求解这两类QOS路由优化问题问题．对第一类问题，求解去掉非线性约束条件后的优化问题．如果找到的解满足非线性约束条件，则该解是最优解；否则在优化问题中添加一个新的线性约束，将已得到的解去掉，反复下去就可得到最终解．对第二类问题，将非线性优化目标换为约束条件中的线性参数，求解此优化模型，如果有解，则记录此时对应的非线性目标值．而后增加一个新的线性约束，去掉刚才得到的解，比较两次得到的非线性目标值，保留最小值．如果得到的解不满足该线性参数的约束条件，则算法结束；否则继续迭代．证明了两种算法的收敛性，并且时间复杂性为近似多项式时间．计算实例表明了算法的有效性．     

一种改进的RM可调度性判定算法

固定优先级任务可调度性判定是实时系统调度理论研究的核心问题之一.目前已有的各种判定方法可归结为两大类:多项式时间调度判定和确切性判定.多项式时间调度判定通常采用调度充分条件来进行,为此,许多理想条件下基于RM(rate monotonic)调度算法的CPU利用率最小上界被提了出来.确切性判定利用RM调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的.但是由于时间复杂度较差,确切性判定方法难以实现在线分析.提出了一种改进的RM可调度性判定方法(improved schedulability test algorithm,简称ISTA).首先介绍了任务调度空间这一概念,并提出了二叉树表示,然后进一步提出了相关的剪枝理论.在此基础上,研究了任务之间可调度性的相关性及其对判定任务集可调度性的影响,提出并证明了相关的定理.最后基于提出的定理,给出了一种改进的伪多项式时间可调度性判定算法,并与已有的判定方法进行了比较.仿真结果表明,该算法平均性能作为任务集内任务个数的函数具有显著提高.     

An Effective Algorithm for the Futile Questioning Problem

In the futile questioning problem, one must decide whether acquisition of additional information can possibly lead to the proof of a conclusion. Solution of that problem demands evaluation of a quantified Boolean formula at the second level of the polynomial hierarchy. The same evaluation problem, called Q-ALL SAT, arises in many other applications. In this paper, we introduce a special subclass of Q-ALL SAT that is at the first level of the polynomial hierarchy. We develop a solution algorithm for the general case that uses a backtracking search and a new form of learning of clauses. Results are reported for two sets of instances involving a robot route problem and a game problem. For these instances, the algorithm is substantially faster than state-of-the-art solvers for quantified Boolean formulas.     

Average-case analysis for the MAX-2SAT problem

We propose a simple probability model for MAX-2SAT instances for discussing the average-case complexity of the MAX-2SAT problem. Our model is a “planted solution model”, where each instance is generated randomly from a target solution. We show that for a large range of parameters, the planted solution (more precisely, one of the planted solution pairs) is the optimal solution for the generated instance with high probability. We then give a simple linear-time algorithm based on a message passing method, and we prove that it solves the MAX-2SAT problem with high probability for random MAX-2SAT instances under this planted solution model for probability parameters within a certain range.     

A BDD SAT solver for satisfiability testing: An industrial case study

The satisfiability problem (SAT) is a fundamental problem in mathematical logic, constraint satisfaction, VLSI engineering, and computing theory. Methods to solve the satisfiability problem play an important role in the development of computing theory and systems. In this paper, we give a BDD (Binary Decision Diagrams) SAT solver for practical asynchronous circuit design. The BDD SAT solver consists of a structural SAT formula preprocessor and a complete, incremental SAT algorithm that is able to find an optimal solution. The preprocessor compresses a large size SAT formula representing the circuit into a number of smaller SAT formulas. This avoids the problem of solving very large SAT formulas. Each small size SAT formula is solved by the BDD SAT algorithm efficiently. Eventually, the results of these subproblems are integrated together that contribute to the solution of the original problem. According to recent industrial assessments, this BDD SAT solver provides solutions to the practical, industrial asynchronous circuit design problems.This research is supported in part by the 1993 ACM/IEEE Design Automation Award, by the Alberta Microelectronics Graduate Scholarship, by the NSERC research grant OGP0046423, and was supported in part by the NSERC strategic grant MEF0045793.Presently, Jun Gu is on leave with the Department of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong.     

求解SAT问题的算法的研究进展

SAT问题是研究最广泛的NPC问题之一。由于SAT问题本身的特性,除非P=NP,否则不存在最坏情况下多项式阶时间复杂度的SAT求解算法。因此设计出高效快速的SAT求解算法至今仍是研究热点。首先简要介绍了SAT问题;其次从完备算法、不完备算法和组合算法3个角度总结了新近的研究进展,深入分析了已有算法解决SAT问题的基本流程,并从适用问题类别、算法特点、求解效率等方面对各类先进的求解器进行了对比分析;最后讨论了求解SAT问题的算法面临的挑战,并对下一步研究工作进行了展望。     

最坏情况下Min-2SAT问题的上界

最坏情况下MaxSAT问题上界的研究已成为一个热门的研究领域.与MaxSAT问题相对的是MinSAT问题,在求解某些组合优化问题时,将其转化为MinSAT问题比转化为MaxSAT问题有着更快的速度,因此对MinSAT问题进行研究.针对Min-2SAT问题提出算法MinSATAlg,该算法首先利用化简算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.从子句数目的角度分析算法的时间复杂度并证明Min-2SAT问题可在O(1.134 3m)时间内求解,对于每个变量至多出现在3个2-子句中的情况,得到最坏情况下的上界为O(1.122 5n),其中n为变量的数目.     

Deciding probabilistic automata weak bisimulation: theory and practice

Weak probabilistic bisimulation on probabilistic automata can be decided by an algorithm that needs to check a polynomial number of linear programming problems encoding weak transitions. It is hence of polynomial complexity. This paper discusses the specific complexity class of the weak probabilistic bisimulation problem, and it considers several practical algorithms and linear programming problem transformations that enable an efficient solution. We then discuss two different implementations of a probabilistic automata weak probabilistic bisimulation minimizer, one of them employing SAT modulo linear arithmetic as the solver technology. Empirical results demonstrate the effectiveness of the minimization approach on standard benchmarks, also highlighting the benefits of compositional minimization.     

Easy Cases of Probabilistic Satisfiability

The Probabilistic Satisfiability problem (PSAT) can be considered as a probabilistic counterpart of the classical SAT problem. In a PSAT instance, each clause in a CNF formula is assigned a probability of being true; the problem consists in checking the consistency of the assigned probabilities. Actually, PSAT turns out to be computationally much harder than SAT, e.g., it remains difficult for some classes of formulas where SAT can be solved in polynomial time. A column generation approach has been proposed in the literature, where the pricing sub-problem reduces to a Weighted Max-SAT problem on the original formula. Here we consider some easy cases of PSAT, where it is possible to give a compact representation of the set of consistent probability assignments. We follow two different approaches, based on two different representations of CNF formulas. First we consider a representation based on directed hypergraphs. By extending a well-known integer programming formulation of SAT and Max-SAT, we solve the case in which the hypergraph does not contain cycles; a linear time algorithm is provided for this case. Then we consider the co-occurrence graph associated with a formula. We provide a solution method for the case in which the co-occurrence graph is a partial 2-tree, and we show how to extend this result to partial k-trees with k>2.     

一个可行的RSA密码破译方法

通过长年研究得到了快速高效的Hamilton路算法。利用多项式规约将3SAT问题转化为对Hamilton路的求解。尽管国际上已有过如何将3SAT问题转化为Hamilton路的方法,但那只是为了证明Hamilton路的NP完全性,因而只要求转化的结果是多项式,而不注重转化效率。为了得到将3SAT直接转化为Hamilton路的高效转化方法,以便有可能通过对后者的高效计算来实现高效计算3SAT,采取用无向图的两个节点模拟3SAT的一个变量,用13个节点的图形结构来模拟3SAT的一个子式的方法,最终实现了上述转化。该转化所需要的节点数及其边数是最优的。将大数的质因子分解转化为对3SAT的求解,从而最终通过求解Hamilton环达到破译RSA密码之目的。     

NP Problem in Quantum Algorithm

In complexity theory, a famous unsolved problem is whether NP is equal to P or not. In this paper, we discuss this aspect in SAT (satisfiability) problem, and it is shown that SAT can be solved in polynomial time by means of a quantum algorithm if the superposition of two orthogonal vectors |0> and |1> prepared is detected physically.     

Solving SAT by Algorithm Transform of Wu s Method

Recently algorithms for solving propositional satisfiability problem, or SAT,have aroused great interest,and more attention has been paid to transformation problem solving.The commonly used transformation is representation transform,but since its intermediate computing procedure is a black box from the viewpoint of the original problem,this approach has many limitations.In this paper,a new approach called algorithm transform is proposed and applied to solving SAT by Wu‘s method,a general algorithm for solving polynomial equations.B y establishing the correspondence between the primitive operation in Wu‘s method and clause resolution is SAT,it is shown that Wu‘s method,when used for solving SAT,,is primarily a restricted clause resolution procedure.While Wu‘s method introduces entirely new concepts.e.g.characteristic set of clauses,to resolution procedure,the complexity result of resolution procedure suggests an exponential lower bound to Wu‘s method for solving general polynomial equations.Moreover,this algorithm transform can help achieve a more efficient implementation of Wu‘s method since it can avoid the complex manipulation of polynomials and can make the best use of domain specific knowledge.