There are many open problems in Computational Complexity Theory.<p><a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P" rel="nofollow">https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P</a><p>It is a difficult subject matter: instead of proving something about a specific program, you must prove results about all possible programs that achieve a task given some set of constraints.<p>IMHO, it is amazing that <i>any</i> results (e.g. [1]) are known at all in that field given how little structure they must work with...<p>Think of this field as the particle physics of CS---not very useful in the real world, but still very cool to learn about.<p>[1] <a href="https://en.wikipedia.org/wiki/PCP_theorem" rel="nofollow">https://en.wikipedia.org/wiki/PCP_theorem</a>
Least known? I think we know the topics even if we aren't good at them.<p>There are lots of medical problems and brain problems and large scale coordination problems we know about but haven't solved or reduced to solvability yet.