On the Complexity of Interoperability
Saikou Y. Diallo · 2016
Interoperability is generally understood as the ability of two or more systems to exchange information and make use of it. The state of the art in interoperability focuses on both the technical infrastructure necessary for information to flow between systems and the semantic alignment of the underlying systems implemented by each system. While there are several definitions of interoperability, there are no formal theories of interoperability that capture 1) what interoperability is as opposed to how it works and 2) how to tell whether two or more systems can interoperate. In this article, we examine whether interoperability can be solved by a computer program and demonstrate that the answer is no because interoperability is Non Polynomial complete.