Finite Playground

To verify is human; to prove, divine.

Directed reachability problem on surface graphs can be solved in poly-time and sub-linear space (!). See the survey by Vinodchandran Variyam.