1
$\begingroup$

Ex.1. Give a Search Problem whose deciding Problem is in co-NP.

Assuming 3SAT is in NP then asking wether a given Boolean formula has a Solution is a search problem in NP right?

Then would asking wether a given Boolean formula has no Solution be in co-NP?

$\endgroup$
  • 1
    $\begingroup$ What do you think? Use the definitions to try and prove that your answer is correct. $\endgroup$ – Yuval Filmus Jun 26 '18 at 15:40
1
$\begingroup$

Specifically speaking, 3-SAT is an example of NP-Complete problem. But your problem is only considered with NP problems.

We have the decision problem:

Is a SAT problem in NP?

Obviously, it is. Because you could always verify a "certificate" in time linear to your input size (values of your literals, that is a sequences of 0s and 1s).

For your question:

Is a un-SAT problem in co-NP? (complement to SAT problem)

We could find the following definition:

A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP [1].

Therefore, un-SAT is co-NP by definition.

$\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.