A solution to the turnpike problem in membranes - Albores, Maria Cristina; Juayong, Richelle Ann. (2009)
P systems are massively parallel computing models that are based on the architecture of living cells; P system variants, namely the P system with active membranes and the P system with membrane creation, have been used to solve NP-complete problems in polynomial time or better by trading time for an exponential workspace. The Turnpike Problem involves the reconstruction of those point sets on a line 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. In this paper, we present a P system with active membranes and membrane creation that implements an O(2[raised to n] n log n)-time backtracking algorithm for the Turnpike Problem in linear time.
Thesis (B.S. Computer Science) -- University of the Philippines, Diliman
Keywords: Biologically-inspired computing; Models, Biological; Molecular biology -- Mathematical models; Turnpike Problem