[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/course/cs254/kbhsu_cs254_jan272025.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- 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’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)