There are many open problems in Computational Complexity Theory. https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P https://complexityzoo.uwaterloo.ca/Complex

There are many open problems in Computational Complexity Theory. https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P 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 https://en.wikipedia.org/wiki/PCP_theorem