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.

2 + 1-local H
NP-complete(19, 20)
2SATCuring strictly
2-local H
In P(20, 21)
MAX2SATEasing strictly
2-local H