Difference between revisions
complexity
Status and infobox
- kind:
—→ region
Source +17 −0
+---
+title: Complexity classes
+kind: region
+space: computation
+---
+The map of how hard problems are. Almost every line on it is conjectured rather than proved.
+
+Mathematics Subject Classification: 68.
+
+## Problems
+
+- [[Problem:p-vs-np|P versus NP]] (open)
+- [[Problem:sensitivity-conjecture|Sensitivity conjecture]] (solved)
+- [[Problem:primes-in-p|PRIMES is in P]] (solved)
+- [[Problem:graph-isomorphism|Graph isomorphism complexity]] (partial)
+
+Part of [[Continent:computation|Computation]].
Revision 59 as rendered
The map of how hard problems are. Almost every line on it is conjectured rather than proved.
Mathematics Subject Classification: 68.
Problems
- P versus NP (open)
- Sensitivity conjecture (solved)
- PRIMES is in P (solved)
- Graph isomorphism complexity (partial)
Part of Computation.