摘要
A one-to-one and onto mapping between the set of conjunctive normal forms and a subset of the potential functions of static electric fields is given; it has been further proved that a conjunctive normal form is satisfiable if and only if there exists a zero point for its corresponding potential function. A particle is always moving in the direction of gradient descent in the field which is the fastest decreasing direction of potential of the particle. Thus, if a conjunctive normal form is satisfiable, the gradient method for its corresponding potential function becomes a fast algorithm to solve its satisfiability problem.
A one-to-one and onto mapping between the set of conjunctive normal forms and a subset of the potential functions of static electric fields is given; it has been further proved that a conjunctive normal form is satisfiable if and only if there exists a zero point for its corresponding potential function. A particle is always moving in the direction of gradient descent in the field which is the fastest decreasing direction of potential of the particle. Thus, if a conjunctive normal form is satisfiable, the gradient method for its corresponding potential function becomes a fast algorithm to solve its satisfiability problem.
基金
Project supported by the Chinese High-Tech Programme and the National Natural Science Foundation of China.
