COMPLEXITY OF VERIFYING JAVA SHARED MEMORY EXECUTION
Alex Gontmakher, Sergey Vladimirovich Polyakov, Assaf Schuster · Parallel Processing Letters · 2003
This paper studies the problem of testing shared memory Java implementations to determine whether the memory behavior they provide is consistent. The complexity of the task is analyzed. The problem is defined as that of analyzing memory access traces. The study showed that the problem is NP-complete, both in the general case and in some particular cases in which the number of memory operations per thread, the number of write operations per variable, and the number of variables are restricted.