For an example of harder-than-np-complete, I was shocked to find out how hard vector reachability is after being presented with a vector reachability problem and assuming I could just look up a reasonable-time algorithm.

I incorrectly assumed it would have some basic linear algebra solution because of how simple the problem seemed.