We show that the problem of predicate detection in distributed
  systems is NP-complete.  We introduce a class of predicates, {\em
    linear predicates}, such that for any linear predicate $B$ there
  exists an efficient detection of the least cut satisfying $B$.  The
  dual of linearity is \emph{post-linearity}.  These 
  properties generalize several known properties of distributed
  systems, such as the set of consistent cuts forms a lattice, and the
  WCP and GCP predicate dectection results given in earlier work.

  We define a more general class of predicates,
  \emph{semi-linear predicates}, for which efficient algorithms are
  known to detect whether a predicate has occurred during an execution
  of a distributed program.  However, these methods may not identify
  the least such cut.  Any stable predicate is an example of a
  semi-linear predicate.  In addition, we show that certain unstable
  predicates can also be semi-linear, such as mutual exclusion
  violation. 

  Finally, we show application of max-flow to the predicate detection
  problem.  This result solves a previously open problem
  in predicate detection, establishing the existence of an efficient
  algorithm to detect predicates of the form $x_1+x_2\ldots+x_N < k$
  where $x_i$ are variables on different processes, $k$ is some
  constant, and $N$ is larger than 2.