Proof that POSITIVE-3-SAT is in the complexity class P

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.

Answer 1

It looks like you misunderstood a bit what you should prove since you missed the much easier way to prove although your (trivial) proof looks correct.

An easier proof

Let us call a boolean formula in conjunctive normal form in which all clauses consist of exactly 3 literals and in which no variable appears negative a positive‑3 formula. So

$$\text{POSITIVE-3-SAT} = \{\langle\phi\rangle \mid \phi\text{ is a satisfiable positive-3 formula}\}.$$

Note that any positive‑3 formula is satisfiable since it becomes TRUE if a truth value of TRUE is assigned to all variables. So

$$\text{POSITIVE-3-SAT} = \{\langle\phi\rangle \mid \phi\text{ is a positive-3 formula}\}.$$

Here is an algorithm $\mathcal A$. Given an input string $s$, $\mathcal A$ just verifies whether $s$ is the encoded form of a positive-3 formula. If $s$ is, $\mathcal A$ returns yes; otherwise, $\mathcal A$ returns no. That verification step can be done in linear time in terms of the number of clauses in $s$. So $\text{POSITIVE-3-SAT}$ is in P.

---

The moral of the above proof is that you can use whatever known to you to construct the algorithm. All you need is to specify an algorithm and show that it works as wanted.

It depends on the requirement/convention/stage of your course or the intention of your course instructor whether you needs to explain in detail why that verification can be done in linear time or polynomial time. It looks like that verification step is totally ignored by the proof in the question, which is, in fact, a general accepted practice in the field.

Answer 2

Yes, your proof seems to be correct. However note that a SAT instance with no negated clause is always satisfable by boolean algebra's axioms, you only need to assign the value "true" to all of them, so your Language is verifiable by definition (it is a bit like prooving that x+y+z+...>0 or xyz*....>0 is always verifiable in Peano's Arithmetic).