  MA is a class of decision problems for which `yes'-instances have a proof
that can be efficiently checked by a classical randomized algorithm. We prove
that MA has a natural complete problem which we call the stoquastic k-SAT
problem. This is a matrix-valued analogue of the satisfiability problem in
which clauses are k-qubit projectors with non-negative matrix elements, while a
satisfying assignment is a vector that belongs to the space spanned by these
projectors. Stoquastic k-SAT is the first non-trivial example of a MA-complete
problem. We also study the minimum eigenvalue problem for local stoquastic
Hamiltonians that was introduced in quant-ph/0606140, stoquastic LH-MIN. A new
complexity class StoqMA is introduced so that stoquastic LH-MIN is
StoqMA-complete. Lastly, we consider the average LH-MIN problem for local
stoquastic Hamiltonians that depend on a random or `quenched disorder'
parameter, stoquastic AV-LH-MIN. We prove that stoquastic AV-LH-MIN is
contained in the complexity class \AM, the class of decision problems for which
yes-instances have a randomized interactive proof with two-way communication
between prover and verifier.
