2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If a problem can be decided in deterministic polynomial time, then this puts it in P. $\endgroup$ – Yuval Filmus Apr 23 at 14:37
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Apr 23 at 16:39
  • $\begingroup$ Perhaps what you really are looking to know is what is the definition of P. If so, see cs.stackexchange.com/q/9556/755 (or a good textbook). $\endgroup$ – D.W. Apr 23 at 16:41
  • $\begingroup$ @D.W. I am not sure that I can rephrase the question in a non yes/no way, but I will try to elaborate on my conceptual difficulty. My specific conceptual question is whether or not the description of the algorithm I have provided is descriptive of an algorithm which sufficiently proves my conclusion. If I were to try and go a bit deeper: I have made a series of claims (... is trivially satisfiable ... , ... can be decided in $O(1)$ steps, ... satisfiability ... in $O(n^1)$ steps). Are these claims consistent with each other and are there any claims missing? $\endgroup$ – Oscar R Apr 23 at 17:41
  • $\begingroup$ Sounds like you want us to check your proof. See cs.meta.stackexchange.com/q/597/755 for why those questions typically don't work well on this site. $\endgroup$ – D.W. Apr 23 at 19:20
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.