Recently algorithms for solving propositional satisfiability problem,or SAT, have aroused great illterest, and more attention has been paid to trans-formation problem solving. The commonly used transformation is repre...Recently algorithms for solving propositional satisfiability problem,or SAT, have aroused great illterest, and more attention has been paid to trans-formation problem solving. The commonly used transformation is representationtransform, but since its ifltermediate computing procedure is a black box from theviewpoint of the original problem, this aPproach has many limitations. In this paper, a new approach called algorithm transform is proposed and applied to solvingSAT by Wu's method, a general algorithm for solving polynomial equations. By es-tablishing the correspondellce between the primitive operation in Wu's method andclause resolution in SAT, it is shown that Wu's method, when used for solving SAT,is primarily a restricted clause resolution procedure. While Wu's method illtroduceselltirely new concepts, e.g. characteristic set of clauses, to resolution procedure, thecomplexity result of resolution procedure suggests an exponential lower bound toWu's method for solving general polynomial equations. Moreover, this algorithmtransform can help achieve a more efficiellt imp1ementation of Wu's method since itcan avoid the complex manipulation of polynomials and can make the best use ofdomain specific knowledge.展开更多
文摘Recently algorithms for solving propositional satisfiability problem,or SAT, have aroused great illterest, and more attention has been paid to trans-formation problem solving. The commonly used transformation is representationtransform, but since its ifltermediate computing procedure is a black box from theviewpoint of the original problem, this aPproach has many limitations. In this paper, a new approach called algorithm transform is proposed and applied to solvingSAT by Wu's method, a general algorithm for solving polynomial equations. By es-tablishing the correspondellce between the primitive operation in Wu's method andclause resolution in SAT, it is shown that Wu's method, when used for solving SAT,is primarily a restricted clause resolution procedure. While Wu's method illtroduceselltirely new concepts, e.g. characteristic set of clauses, to resolution procedure, thecomplexity result of resolution procedure suggests an exponential lower bound toWu's method for solving general polynomial equations. Moreover, this algorithmtransform can help achieve a more efficiellt imp1ementation of Wu's method since itcan avoid the complex manipulation of polynomials and can make the best use ofdomain specific knowledge.
