Let's determine if an expression is tautological or not and let's try this expression: ((a ⊼ b) ∨ c) ↔ (¬a ∨ ¬b ∨ c). We can turn this problem into CIRCUIT-SAT decision problem by asking if the expression ((a ⊼ b) ∨ c) ⊕ (¬a ∨ ¬b ∨ c) is satisfiable. Note that we repalced the universal gate with its inverse (by "universal" I mean the gate that be computed the last). And now since we figured out that this expression isn't satisfiable then we can say that its (inverse) is tautological. Isn't this enough to conclude that NP = co-NP? Isn't UNSAT simply is where we take the answer to SAT and we apply an inverter on it?

  • 2
    $\begingroup$ Asked and answered before. In short, if you insert the answer then you get a trivial language rather than coSAT. $\endgroup$ Commented Jun 21, 2022 at 14:16
  • $\begingroup$ @YuvalFilmus Unfortunately I didn't understand what do you mean. Isn't the decision problem gives an answer of yes or no (accepted or denied)? What do you mean by "a trivial language" and by "coSAT" here?! And I'm sorry for taking your time. $\endgroup$
    – Prometheus
    Commented Jun 21, 2022 at 18:35
  • $\begingroup$ Hopefully someone will provide a link for an existing answer which tackles the very same issue. $\endgroup$ Commented Jun 21, 2022 at 20:23
  • $\begingroup$ @YuvalFilmus I hope that too! Thank you anyway! $\endgroup$
    – Prometheus
    Commented Jun 21, 2022 at 20:35
  • $\begingroup$ Maybe this helps. cs.stackexchange.com/questions/128148/why-isnt-sat-in-conp $\endgroup$
    – Janmar
    Commented Jun 22, 2022 at 15:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.