The P versus NP problem: Unconventional insights from Membrane Computing

Abstract

: The P ?=NP question is one of the outstanding open problems in theoretical computer science. The relevance of this question is not only the inherent pleasure of solving a mathematical problem, since an answer to it would provide information of high economical interest. On the one hand, a negative answer to this question would confirm that the majority of current cryptographic systems are secure from a practical point of view. On the other hand, a positive answer would not only show the uncertainty about the secureness of these systems, but also this kind of answer is expected to come together with a general procedure such that it will provide a deterministic algorithm solving any NP-complete problem in polynomial time. In this talk, new approaches/tools to attack the previous problem are given by using Membrane Computing, a branch of Natural Computing aiming to abstract computing models from the structure and functioning of the living cell as well as from the organization of cells in tissues, organs, and other higher order structures. The devices of this paradigm constitute models for distributed, parallel and non-deterministic computing. Specifically, different borderlines between efficiency and non-efficiency are shown in terms of syntactical ingredients of cell-like and tissue like membrane systems. Each of them provide appealing characterizations of the P̸=NP conjecture within the framework of this bioinspired and unconventional computing model.