SU-CS254 JAN272025

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)