0
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks so much for the answer, how do you know when it belongs to conp and when to np? $\endgroup$
    – dust
    Jul 19, 2021 at 20:21
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Jul 19, 2021 at 20:26
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Jul 19, 2021 at 20:27
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    Jul 19, 2021 at 20:31
  • $\begingroup$ Thanks, if I understood correctly, because we need to show that something is not satisfy, then it's a co-np? $\endgroup$
    – dust
    Jul 19, 2021 at 20:41

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.