This paper considers the decision problem for the existential fragment of the theory of simplification orderings. A simple, polynomialtime procedure is given for deciding satisfiability of ordering constraints by simplification orderings, and it is also shown that the corresponding problem for total simplification orderings is NP-complete. This latter result can be interpreted as showing that the problem of deciding whether or not a simplification ordering on first-order terms can be linearized is NP-complete.