1
$\begingroup$

I'm trying to understand the very simple concept of co-NP but I can't figure it out. On wikipedia, it gives the example of SAT and its complement:

The complement of any problem in NP is a problem in co-NP. An example of an NP-complete problem is the circuit satisfiability problem: given a Boolean circuit, is there a possible input for which the circuit outputs true? The complementary problem asks: "given a Boolean circuit, do all possible inputs to the circuit output false?". This is in co-NP because a polynomial-time certificate of a no-instance is a set of inputs which make the output true.

I understand the difference with the certificates, but isn't SAT and "co-SAT" the exact same problem? I mean say we have an algorithm that solves SAT, wouldn't that exact same algorithm solve co-SAT as well by simply composing it with a constant time function that inverts a "YES" to a "NO"? And if they are the exact same problem, why are they in different complexity classes? What is the point of co-NP?

$\endgroup$
0

0

Browse other questions tagged or ask your own question.