---
title: "SU-CS254 JAN272025"
source: https://www.jemoka.com/posts/kbhsu_cs254_jan272025/
date: 2025-01-27
---

Key Sequence Notation A Library of Languages New Concepts coNP UNSAT coNP complete NP intersect coNP some languages PERFECT-MATCHING PRIMES FACTORING Important Results / Claims SAT is in NP if \(\text{P}= \text{NP}\), then \(\text{NP} = \text{coNP}\) (ARROW GOES ONE WAY) notice also the contrapositive \(\text{NP} \neq \text{coNP} \implies P \neq NP\). UNSAT is coNP-complete Hall&rsquo;s Theorem and Not Hall&rsquo;s Theorem Interesting Factoids \(L\) is NP complete IFF \(\neg L\) is coNP complete. some open problems&hellip; does \(\text{NP} = \text{coNP}\) does NP intersect coNP equal to P? (Does having efficiently checkable proofs for both pretense and absence in a set imply we can actually proof it efficiently.) Edmond&rsquo;s Conjectures \(\text{NP} \neq \text{coNP}\) &ldquo;probably easy and not trilling&rdquo; (which is very wrong) \(\text{NP} \cap \text{coNP} = P\) &ldquo;trilling&rdquo; (which is true)
