Question

I have the following language:

$$\text{POSITIVE-3-SAT} = \{\langle\phi\rangle \mid \phi\text{ is a satisfiable boolean formula in conjunctive normal form,}\\ \text{ in which all clauses consist of exactly 3 literals and in which no variable appears negated}\}.$$


Progress so far:

My concern is that I have not understood the task. I have proposed what I think is a (near trivial) proof.

To show that the language is in P, my approach is to provide a deterministic algorithm which can decide the problem in polynomial time.

By definition, $\text{POSITIVE-3-SAT}$ must comprise of an arbitrarily long number of conjunctions of clauses of the form $(\lambda_1 \lor \lambda_2 \lor \lambda_3)$. Each clause is trivially satisfiable in the case that a truth value of TRUE is assigned to any of the clauses $\lambda_1, \lambda_2, \lambda_3$. On this basis, each clause containing 3 literals can be decided in $O(3)$ steps, $\equiv O(1)$.

If we make the assumption that the language is constrained to only contain a finite number of $n$ clauses, then we can say that the satisfiability of the language can be decided in $O(n) \equiv O(n^1)$ steps.

Thus, $\text{POSITIVE-3-SAT}$ can be decided by a deterministic algorithm in polynomial time.

Thus, $\text{POSITIVE-3-SAT} \in$ NP.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top