The complexity of verifying memory coherence
Jason F. Cantin, Mikko H. Lipasti, James E. Smith · 2003
The general problem of verifying coherence for shared-memory multiprocessor executions is NP-Complete. Verifying memory consistency models is therefore NP-Hard, because memory consistency models require coherence for some or all operations. However, verifying memory consistency remains NP-Complete for executions known to be coherent.