[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/np_intersect_conp.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "NP intersect coNP" type: concept source: https://www.jemoka.com/posts/kbhnp_intersect_conp/ confidence: high status: active --- \(\text{NP} \cap \text{coNP}: \forall x \in \qty {0,1}^{*}, \exists\) short, efficiently checkable proof of BOTH \(x\) presence/absence in \(L\) some examples in P: PERFECT-MATCHING in P: PRIMES we don’t know if this is in \(P\): FACTORING … if it was, much of cryptography will break