# How to know if language is in comp or np?

I'm new to the site.

I had a test a few days ago and failed it, I had a question I did not understand.

This is the question:

Let's look at the FALSE language: Collect all the verses P in the form of CNF so that any placement on the variables P will not satisfy P. We will mark the number of variables in N and the number of verses in M. Determine which of the following statements is correct:

1. The language is in P. You can build an algorithm running in time O (max{N^5, M*N}^2)
2. The language is in NP.
3. The language is in CONP.

How do I know what the correct answer to the question is? How can I tell if the FALSE language belongs to np or conp I do not understand.

• – D.W.
Commented Oct 26, 2021 at 3:16

I assume that by "verses" you mean boolean formulas.

The language is definitely in CO-NP since a "no" certificate is a satisfying assignment.

Currently we don't know whether FALSE is in P nor whether it is in NP.

• Thanks so much for the answer, how do you know when it belongs to conp and when to np?
– hch
Commented Jul 19, 2021 at 20:21
• There is no "mechanical" way to know. To show that it is in NP you need to find a non-deterministic polynomial-time algorithm that solves the problem. Equivalently you can show that if the instance is a "yes" instance then there is a certificate of at most polynomial length (in the input instance) and a deterministic polynomial-time algorithm that receives an instance and a "candidate" certificate as input. If the instance is a "yes"-instance and the certificate is valid, the algorithm must return "yes". If the instance is a "no"-instance then the algorithm must return no. Commented Jul 19, 2021 at 20:26
• To show that a problem is in CO-NP the same discussion as above holds but you consider the complementary problem. Essentially the certificate becomes a "no" certificate for the original problem. Commented Jul 19, 2021 at 20:27
• In your particular case, SAT is a well-known NP-Complete problem and FALSE is its complement. Therefore FALSE is CO-NP complete and, in particular, it is in CO-NP. We don't know whether CO-NP=NP or whether P=NP=CO-NP. Commented Jul 19, 2021 at 20:31
• Thanks, if I understood correctly, because we need to show that something is not satisfy, then it's a co-np?
– hch
Commented Jul 19, 2021 at 20:41