Using Clausal Graphs to Determine the Computational Complexity of k-Bounded Positive 1-in-3 SAT

Title

Using Clausal Graphs to Determine the Computational Complexity of k-Bounded Positive 1-in-3 SAT

Creator

Denman, Richard

Foster, Stephen

Date

2014-09-02

Date Available

2014-09-02

Date Issued

2008

uri

http://collections.southwestern.edu/s/suscholar/item/3

Abstract

The 1-in-3 SAT problem is known to be NP-complete even in the absence of negated variables [1], a variant known as Positive (or Monotone) 1-in-3 SAT. In this note, we use clausal graphs to investigate a further restriction: k- Bounded-Positive 1-in-3 SAT (kBP 1-in-3 SAT), in which each variable occurs in no more than k clauses. We show that for k = 2, kBP 1-in-3 SAT is in the polynomial complexity class P, while for all k>2, it is NP-complete, providing another way of exploring the boundary between classes P and NP.

Language

English

Relation

Brown Working Papers in the Arts and Sciences; 2008, no.2

Subject

Clausal graphs

k-Bounded Positive 1-in-3 SAT

Polynomial complexity

NP-complete

Type

Working Paper