A mathematic-physical approach to the satisfiability problem

  • Li Wei*
  • , Huang Wenqi
  • *Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

A one-to-one and onto mapping between the set of conjunctive normal forms and a subset of the potential functions of static electric field sis 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.

Original languageEnglish
Pages (from-to)116-128
Number of pages13
JournalScience in China Series A-Mathematics Physics Astronomy and Technological Science
Volume38
Issue number1
StatePublished - Jan 1995

Keywords

  • gradient method
  • potential functions
  • satisfiability
  • static electric fields

Fingerprint

Dive into the research topics of 'A mathematic-physical approach to the satisfiability problem'. Together they form a unique fingerprint.

Cite this