robryk
Joined 13 years ago
Karma
1,089
Submissions
540
Member since
Jun 11
Joined 13 years ago
These are by far not most, nor most of the practically useful ones. Directed graph reachability, given an adjacency list as input, is NL-hard.
E: The obvious way to fix this is to stop talking about messages existing/not existing, but talk in terms of messages being stored in X (or having been deleted from X), for some value of X.
You can reach me at @robryk:wuatek.is