Topic for Today : Solving Computationally Hard Problems in Polynomial Time
The computational power (the “competence”) is only one of the important questions to be dealt with when defining a new computing model. The other fundamental question concerns the computing efficiency, t he resources used for solving problems. In general, the research in natural computing is especially concerned with this issue. Because P systems are parallel computing devices, it is expected that they can solve hard problems in an efficient manner – and this expectation is confirmed for systems provided with ways for producing an exponential workspace in a linear time.
We have discussed above three basic ways to construct such an exponential space in cell-like P systems, namely, membrane division (the same effect has the separation operation, as well as other operations which replicate partially or totally the contents of a membrane), membrane creation (combined with the creation of exponentially many objects), and string replication.
Similar possibilities are offered by cell division in tissue-like systems and by objects replication in neural-like systems. Also the possibility to use a pre-computed exponential work space, unstructured and non-active (e.g., with the regions containing no object) was considered.
In all these cases polynomial or pseudo–polynomial solutions to NP-complete problems were obtained. The first problem addressed in this context was SAT [81], [79] (the solution was improved in several respects in other subsequent papers), but similar solutions are reported in the literature for the Hamiltonian Path problem, the Node Covering problem, the problem of inverting one-way functions, the Subset-sum, and the Knapsack problems.
This direction of research is very active at the present moment. More and more problems are considered, the membrane computing complexity classes are refined, characterizations of the P6=NP conjecture were obtained in this framework, improvements are looked for.
Mentioned already the intriguing question whether polynomial solutions to NP-complete problems can be obtained through P sys tems with active membranes without polarizations (and without label changing possibilities of other additional features). In general, the borderline between efficiency (the possibility to solve NP-complete problems in polynomial time) and non-efficiency is a challenging topic. Anyway, we know that membrane division cannot be avoided (“Milano theorem”: a P system without membrane division can be simulated by a Turing machine with a polynomial slowdown.
