Аннотация:The provability problem for the Horn fragment of linear logic is NP-complete. In this work we investigate various definitions of concurrency proposed in and establish the complexity of the provability problem and the problem of concurrency recognition. The notion of k-maximal concurrency is introduced which guarantees polynomial time provability. Theorems on hierarchy and on complexity of recognition of the property are proved.