Index Terms

We study the problem of testing shared memories for violations of memory coherence and consistency. We first prove that detecting violations of coherence in an execution is NP-Complete, and show that it remains NP-Complete for a number of very restricted instances. We then use this result to prove that all known consistency models are NP-Hard to verify. Finally, we show that the complexity of verifying consistency models is not a mere consequence of coherence, and that verifying sequential consistency remains NP-Complete once coherence has been verified.