3SAT analogous problem in P
You might find Greenlaw, Hoover and Ruzzo's "Limits to Parallel Computation: P-Completeness Theory" interesting. It obviously goes a lot further than the limits of this question, but most pertinently includes in Appendix A a compendium of P-complete problems in the style of Garey &amp; Johnson. There are far too many to be worth listing here, but some key ("interesting") problems are:


The Circuit Value Problem
Linear Inequalities (this is one way to get a decision version of Linear Programming)
Maximum Flow
Context-free Grammar Membership
Point Location on a Convex Hull