Comment by fooker

Interestingly being P complete has another unexpected consequence: it means your problem is going to be difficult to parallelize.

This is why parallel SAT solvers are barely faster than the usual ones.

SAT is NP complete, but a crucial step in SAT solving (unit propagation) is P complete.