Loading...
Please wait, while we are loading the content...
Similar Documents
k-Bounded Positive Not All Equal LE3-SAT
| Content Provider | Semantic Scholar |
|---|---|
| Author | Anthony, Barbara M. Denman, Richard |
| Copyright Year | 2009 |
| Abstract | The not all equal (NAE) 3-SAT problem is known to be NP-complete even in the absence of negated variables (see [11]), a variant known as positive (or monotone) NAE 3-SAT. In this article, we investigate a related category, dubbed positive NAE LE3SAT (PNAE LE3-SAT), in which each clause has at most three variables, none of which is negated, and an assignment is sought that will satisfy such an expression in a way that meets the NAE restriction. We show that PNAE LE3-SAT is NP-complete even when no variable occurs more than three times (3B-PNAE LE3-SAT), and that PNAE LE3-SAT is in complexity class P when no variable occurs more than twice (2B-PNAE LE3-SAT). |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.southwestern.edu/academics/bwp/vol9/denman-vol9.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
