完全问题可以视为类内最难的问题。因此证明等价于证明一个完全问题不能在（确定）对数空间内判定。

最著名的完全问题是有向图上的连通性问题（directed st connectivity）：给定有向图及其两个节点和，判定是否包含一条由至的有向路径。它的一些常见变种（variants）也是完全的：①判断有向图是否强连通（strongly connected）。②给定有向图及其两个节点和，和自然数，判定是否包含一条由至长度不超过的有向路径。

有趣的是，②的无向图版本，即判断无向图是否包含一条由至长度不超过的有向路径也是完全的。而没有长度的限制后，基于Reingold算法，无向图的连通性问题 （undirected stconnectivity）是对数空间完全的。

另一个重要的完全问题是2-SAT：给定一个合取范式（conjunctive normal form, CNF）公式，其中每个子句包含至多2个文字（literal），判定此公式是否可满足。