A Linear Time Complexity of Breadth-First Search Using P System with Membrane Division

الملخص EN

One of the known methods for solving the problems with exponential time complexity such as NP-complete problems is using the brute force algorithms.

Recently, a new parallel computational framework called Membrane Computing is introduced which can be applied in brute force algorithms.

The usual way to find a solution for the problems with exponential time complexity with Membrane Computing techniques is by P System with active membrane using division rule.

It makes an exponential workspace and solves the problems with exponential complexity in a polynomial (even linear) time.

On the other hand, searching is currently one of the most used methods for finding solution for problems in real life, that the blind search algorithms are accurate, but their time complexity is exponential such as breadth-first search (BFS) algorithm.

In this paper, we proposed a new approach for implementation of BFS by using P system with division rule technique for first time.

The theorem shows time complexity of BSF in this framework on randomly binary trees reduced from O(2d) to O(d).