<p>There are a number of satisfiability problems that are difficult to solve even in the fixed parameter sense. For example, Weighted q-CNF Satisfiability is W[1]-complete when parameterized by the number of variables that are set to true.</p>

<p>My question is: is there any literature on whether Positive 1-in-3 is W[1]-hard or fixed parameter tractable when parameterized by the number of variables that are set to true? Positive 1-in-3 SAT is the problem where all literals in an expression are positive and <em>exactly</em> one literal in each clause is true.</p>

<np-hardness><sat><parameterized-complexity>
Positive 1-in-3 SAT FPT or Fixed Parameter Intractable
user1246462
# Positive 1-in-3 SAT FPT or Fixed Parameter Intractable

(Asked by: username_0 on 2016-09-04)

There are a number of satisfiability problems that are difficult to solve even in the fixed parameter sense. For example, Weighted q-CNF Satisfiability is W[1]-complete when parameterized by the number of variables that are set to true.

My question is: is there any literature on whether Positive 1-in-3 is W[1]-hard or fixed parameter tractable when parameterized by the number of variables that are set to true? Positive 1-in-3 SAT is the problem where all literals in an expression are positive and *exactly* one literal in each clause is true.

**Tags:** np-hardness, sat, parameterized-complexity


---

## 0 answers

