[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/sat_is_in_np.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "SAT is in NP" type: concept related: [Non Polynomial Time] source: https://www.jemoka.com/posts/kbhsat_is_in_np/ confidence: high status: active --- Recall SAT is in NP because if \(\phi \in \text{SAT}\), then there is a short (poly-n space), efficiently (poly-time) checkable proof (by just reading out the satisfying assignment).