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’s Theorem and Not Hall’s Theorem Interesting Factoids L is NP complete IFF \neg L is coNP complete. some open problems… 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’s Conjectures \text{NP} \neq \text{coNP} “probably easy and not trilling” (which is very wrong) \text{NP} \cap \text{coNP} = P “trilling” (which is true)