Intractability results in predicate detection

We also explore the tractability of linear and regular predicates. In particular, we show that, unless RP=NP, there is no polynomial-time algorithm to detect possibly:B for linear and regular predicates B.