An implementation of a backtracking algorithm for the turnpike problem in membranes - Albores, Maria Cristina (Philippine computing journal)
The goal of the Turnpike Problem is to reconstruct those point sets that arise from a given distance multiset. Although the Turnpike Problem itself is of unknown complexity, variants of it have been proven to be NP-complete, and there are no existing polynomial algorithms for it. P systems with active membranes and P systems with membrane creation are parallel computing models based on the characteristics of living cells; both have been used to solve NPcomplete problems in polynomial time or better by trading time for an exponential workspace. In this paper we present a P system with active membranes and membrane creation that implements an O(2nn log n)-time backtracking algorithm for the Turnpike Problem in linear time.