Table 1 Analogy between satisfiability problems and curing/easing the sign problem.

The satisfiability equivalent of curing the sign problem is to decide whether a given sentence is satisfiable, while the equivalent of easing is to find the minimal number of clauses that are violated by a sentence. Similarly, results on the computational complexity of curing and easing the non-stoquasticity of a local Hamiltonian H are in one-to-one correspondence with the hardness of satisfiability problems.