A physical model for the satisfiability problem

Huang Wenqi; Li Wei; Lu Weifeng; Zhang Yuping

doi:10.1007/BFb0030881

A physical model for the satisfiability problem

Huang Wenqi
, Li Wei
, Lu Weifeng
, Zhang Yuping

School of Computer Science and Engineering

Huazhong University of Science and Technology
Beihang University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

An one to one and onto mapping between the set of conjunctive normal forms and a subset of the potential functions of static electricity fields is constructed; and it has been further proved that a conjunctive normal form is satisfiable if and only if the minimum of the corresponding potential function is zero. It is also shown that the local search method has the same physical model as the gradient method given in this paper.

Original language	English
Title of host publication	Computing and Combinatorics - 1st Annual International Conference, COCOON 1995, Proceedings
Editors	Ding-Zhu Du, Ming Li, Ding-Zhu Du
Publisher	Springer Verlag
Pages	591-596
Number of pages	6
ISBN (Print)	354060216X, 9783540602163
DOIs	https://doi.org/10.1007/BFb0030881
State	Published - 1995
Event	1st Annual International Computing and Combinatorics Conference, COCOON 1995 - Xi’an, China Duration: 24 Aug 1995 → 26 Aug 1995

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	959
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st Annual International Computing and Combinatorics Conference, COCOON 1995
Country/Territory	China
City	Xi’an
Period	24/08/95 → 26/08/95

Access to Document

10.1007/BFb0030881

Cite this

Wenqi, H., Wei, L., Weifeng, L., & Yuping, Z. (1995). A physical model for the satisfiability problem. In D.-Z. Du, M. Li, & D.-Z. Du (Eds.), Computing and Combinatorics - 1st Annual International Conference, COCOON 1995, Proceedings (pp. 591-596). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 959). Springer Verlag. https://doi.org/10.1007/BFb0030881

Wenqi, Huang ; Wei, Li ; Weifeng, Lu et al. / A physical model for the satisfiability problem. Computing and Combinatorics - 1st Annual International Conference, COCOON 1995, Proceedings. editor / Ding-Zhu Du ; Ming Li ; Ding-Zhu Du. Springer Verlag, 1995. pp. 591-596 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{16275d16266d4722a1e88099ed5c135a,

title = "A physical model for the satisfiability problem",

abstract = "An one to one and onto mapping between the set of conjunctive normal forms and a subset of the potential functions of static electricity fields is constructed; and it has been further proved that a conjunctive normal form is satisfiable if and only if the minimum of the corresponding potential function is zero. It is also shown that the local search method has the same physical model as the gradient method given in this paper.",

author = "Huang Wenqi and Li Wei and Lu Weifeng and Zhang Yuping",

note = "Publisher Copyright: {\textcopyright} 1995, Springer-Verlag. All Rights Reserved.; 1st Annual International Computing and Combinatorics Conference, COCOON 1995 ; Conference date: 24-08-1995 Through 26-08-1995",

year = "1995",

doi = "10.1007/BFb0030881",

language = "英语",

isbn = "354060216X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "591--596",

editor = "Ding-Zhu Du and Ming Li and Ding-Zhu Du",

booktitle = "Computing and Combinatorics - 1st Annual International Conference, COCOON 1995, Proceedings",

address = "德国",

}

Wenqi, H, Wei, L, Weifeng, L & Yuping, Z 1995, A physical model for the satisfiability problem. in D-Z Du, M Li & D-Z Du (eds), Computing and Combinatorics - 1st Annual International Conference, COCOON 1995, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 959, Springer Verlag, pp. 591-596, 1st Annual International Computing and Combinatorics Conference, COCOON 1995, Xi’an, China, 24/08/95. https://doi.org/10.1007/BFb0030881

A physical model for the satisfiability problem. / Wenqi, Huang; Wei, Li; Weifeng, Lu et al.
Computing and Combinatorics - 1st Annual International Conference, COCOON 1995, Proceedings. ed. / Ding-Zhu Du; Ming Li; Ding-Zhu Du. Springer Verlag, 1995. p. 591-596 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 959).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A physical model for the satisfiability problem

AU - Wenqi, Huang

AU - Wei, Li

AU - Weifeng, Lu

AU - Yuping, Zhang

PY - 1995

Y1 - 1995

N2 - An one to one and onto mapping between the set of conjunctive normal forms and a subset of the potential functions of static electricity fields is constructed; and it has been further proved that a conjunctive normal form is satisfiable if and only if the minimum of the corresponding potential function is zero. It is also shown that the local search method has the same physical model as the gradient method given in this paper.

AB - An one to one and onto mapping between the set of conjunctive normal forms and a subset of the potential functions of static electricity fields is constructed; and it has been further proved that a conjunctive normal form is satisfiable if and only if the minimum of the corresponding potential function is zero. It is also shown that the local search method has the same physical model as the gradient method given in this paper.

UR - https://www.scopus.com/pages/publications/84957589595

U2 - 10.1007/BFb0030881

DO - 10.1007/BFb0030881

M3 - 会议稿件

AN - SCOPUS:84957589595

SN - 354060216X

SN - 9783540602163

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 591

EP - 596

BT - Computing and Combinatorics - 1st Annual International Conference, COCOON 1995, Proceedings

A2 - Du, Ding-Zhu

A2 - Li, Ming

A2 - Du, Ding-Zhu

PB - Springer Verlag

T2 - 1st Annual International Computing and Combinatorics Conference, COCOON 1995

Y2 - 24 August 1995 through 26 August 1995

ER -

Wenqi H, Wei L, Weifeng L, Yuping Z. A physical model for the satisfiability problem. In Du DZ, Li M, Du DZ, editors, Computing and Combinatorics - 1st Annual International Conference, COCOON 1995, Proceedings. Springer Verlag. 1995. p. 591-596. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0030881

A physical model for the satisfiability problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this