---
title: "Provability"
type: concept
source: https://www.jemoka.com/posts/kbhprovability/
confidence: high
status: active
---

Coping with NP Completeness It&rsquo;s possible to solve NP complete problems!
average case/worst case complexity: it&rsquo;s possible to solve SAT for a lot of problems which solves the average case problems (&ldquo;Heuristics vs. Algorithms&rdquo;) special cases: 2SAT, subset sum, etc. can be solved in very special cases
