k-Bounded Positive Not All Equal LE3-SAT

Title

k-Bounded Positive Not All Equal LE3-SAT

Creator

Anthony, Barbara M.

Denman, Richard

Date

2014-08-29

Date Available

2014-08-29

Date Issued

2009

uri

https://collections.southwestern.edu/s/suscholar/item/5

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).

Language

English

Relation

Brown Working Papers in the Arts and Sciences; 2009, no.1

Subject

Positive NAE 3-SAT

Clausal graphs

Polynomial complexity

NP-complete

Nondeterministic polynomial complexity

Type

Working Paper