Least known? I think we know the topics even if we aren't good at them.
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.
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.
IMHO, it is amazing that any results (e.g. [1]) are known at all in that field given how little structure they must work with...
Think of this field as the particle physics of CS---not very useful in the real world, but still very cool to learn about.
3 comments
[ 3.3 ms ] story [ 18.0 ms ] threadThere 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.
https://complexityzoo.uwaterloo.ca/Complexity_Zoo: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.
IMHO, it is amazing that any results (e.g. [1]) are known at all in that field given how little structure they must work with...
Think of this field as the particle physics of CS---not very useful in the real world, but still very cool to learn about.
[1] https://en.wikipedia.org/wiki/PCP_theorem