Loading...
Please wait, while we are loading the content...
Similar Documents
Volume ix (2009) k-bounded positive not all equal le3-sat (2010).
| Content Provider | CiteSeerX |
|---|---|
| Author | Anthony, Barbara M. Denman, Richard |
| 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 LE3-SAT (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 | |
| Publisher Date | 2010-01-01 |
| Access Restriction | Open |
| Subject Keyword | Equal Le3-sat Pnae Le3-sat Volume Ix Nae Restriction Positive Nae Le3-sat 3b-pnae Le3-sat Complexity Class 2b-pnae Le3-sat Negated Variable Related Category |
| Content Type | Text |
