The Library
Boundary properties of the satisfiability problems
Tools
Lozin, Vadim V. and Purcell, Christopher (2013) Boundary properties of the satisfiability problems. Information Processing Letters, Volume 113 (Number 9). pp. 313-317. doi:10.1016/j.ipl.2013.01.022 ISSN 0020-0190.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.ipl.2013.01.022
Abstract
The satisfiability problem is known to be NP-complete in general and for many restricted instances, such as CNF formulas with at most 3 variables per clause and at most 3 occurrences per variable, or planar formulas. The latter example refers to graphs representing satisfiability instances. These are bipartite graphs with vertices representing clauses and variables, and edges connecting variables to the clauses containing them. Finding the strongest possible restrictions under which the problem remains NP-complete is important for at least two reasons. First, this can make it easier to establish the NP-completeness of new problems by allowing easier transformations. Second, this can help clarify the boundary between tractable and intractable instances of the problem. In this paper, we address the second issue and reveal the first boundary property of graphs representing satisfiability instances.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Information Processing Letters | ||||
Publisher: | Elsevier BV | ||||
ISSN: | 0020-0190 | ||||
Official Date: | 15 May 2013 | ||||
Dates: |
|
||||
Volume: | Volume 113 | ||||
Number: | Number 9 | ||||
Page Range: | pp. 313-317 | ||||
DOI: | 10.1016/j.ipl.2013.01.022 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |