Uniformity is Weaker than Semi-Uniformity for Some Membrane Systems

• Autorzy: Murphy N. , Woods D.

Identyfikatory

DOI

10.3233/FI-2014-1095

• Języki publikacji: EN

Abstrakty

EN

We investigate computing models that are presented as families of finite computing devices with a uniformity condition on the entire family. Examples of such models include Boolean circuits, membrane systems, DNA computers, chemical reaction networks and tile assembly systems, and there are many others. However, in such models there are actually two distinct kinds of uniformity condition. The first is the most common and well-understood, where each input length is mapped to a single computing device (e.g. a Boolean circuit) that computes on the finite set of inputs of that length. The second, called semi-uniformity, is where each input is mapped to a computing device for that input (e.g. a circuit with the input encoded as constants). The former notion is well-known and used in Boolean circuit complexity, while the latter notion is frequently found in literature on nature-inspired computation from the past 20 years or so. Are these two notions distinct? For many models it has been found that these notions are in fact the same, in the sense that the choice of uniformity or semi-uniformity leads to characterisations of the same complexity classes. In other related work, we showed that these notions are actually distinct for certain classes of Boolean circuits. Here, we give analogous results for membrane systems by showing that certain classes of uniform membrane systems are strictly weaker than the analogous semi-uniform classes. This solves a known open problem in the theory of membrane systems. We then go on to present results towards characterising the power of these semi-uniform and uniform membranemodels in terms of NL and languages reducible to the unary languages in NL, respectively.

Słowa kluczowe

EN

membranes systems; computational complexity; uniform families; semi-uniform families; tally languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 134, nr 1/2
• Strony: 129--152
• Opis fizyczny: Bibliogr. 60 poz., rys.

Twórcy

autor

Murphy N.

• Microsoft Research, Cambridge, CB1 2FB, UK

autor

Woods D.

• California Institute of Technology, Pasadena, CA 91125, USA

Bibliografia

• [1] Adleman, L.: Molecular computation of solutions to combinatorial problems, Science, 266, 1994, 1021–1024.
• [2] Alhazov, A., Martín-Vide, C., Pan, L.: Solving a PSPACE-Complete Problem by Recognizing P Systems with Restricted Active Membranes, Fundamenta Informaticae, 58(2), 2003, 67–77.
• [3] Alhazov, A., Pan, L.: Polarization less P Systems with active membranes, Grammars, 7, 2004, 141–159.
• [4] Alhazov, A., Pérez-Jimnez,M. J.: Uniform Solution to QSAT Using Polarizationless Active Membranes, in: Machines, Computations and Universality (MCU), vol. 4664 of Lecture Notes in Computer Science, Springer,2007, 122–133.
• [5] Allender, E., Koucký, M.: Amplifying lower bounds by means of self-reducibility, Journal of the ACM, 57,March 2010, 14:1–14:36.
• [6] Allender, E., Lange, K.-J.: RUSPACE(log n) ⊆ DSPACE(log2 n/ log log n), Theory of Computing Systems,31(5), 1998, 539–550.
• [7] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009,ISBN 978-0-511-53381-5.
• [8] Barish, R. D., Rothemund, P. W. K., Winfree, E.: Two computational primitives for algorithmic self assembly: copying and counting, Nano Lett., 5, 2005, 2586–2592.
• [9] Barish, R. D., Schulman, R., Rothemund, P. W. K., Winfree, E.: An information-bearing seed for nucleating algorithmic self-assembly, PNAS, 106(15), 2009, 6054–6059.
• [10] Book, R. V., Ko, K.-I.: On sets truth-table reducible to sparse sets, SIAM Journal of Computing, 17(5), 1988,903–919.
• [11] Borodin, A.: On relating time and space to size and depth, SIAM Journal on Computing, 6(4), 1977, 733–744.
• [12] Buhrman, H., Hemaspaandra, E., Longpre, L.: SPARSE reduces conjunctively to TALLY, SIAM Journal of Computing, 24, June 1995, 673–681.
• [13] Cai, J.-Y., Sivakumar, D.: Resolution of Hartmanis’ conjecture for NL-hard sparse sets, Theoretical Computer Science, 240(2), 2000, 257 – 269.
• [14] Chandra, A. K., Stockmeyer, L. J., Vishkin, U.: Constant depth reducibility, SIAM Journal of Computing,13(2), 1984, 423–439.
• [15] Chen, H.-L., Doty, D., Holden, D., Thachuk, C., Woods, D., Yang, C.-T.: Fast algorithmic self-assembly of simple shapes using random agitation, DNA20: The 20th International Conference on DNA Computing and Molecular Programming, LNCS, Springer, Kyoto, Japan, September 2014.
• [16] Condon, A., Hu, A. J., Maňuch, J., Thachuk, C.: Less haste, less waste: on recycling and its limits in stranddisplacement systems, Journal of the Royal Society – Interface focus, 2(4), 2012, 512–521.
• [17] Cook, M., Soloveichik, D., Winfree, E., Bruck, J.: Programmability of Chemical Reaction Networks, in: Algorithmic Bioprocesses, Springer, 2009, 543–584.
• [18] Dabby, N., Chen, H.-L.: Active self-assembly of simple units using an insertion primitive, SODA: Proceedings of the Twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2012.
• [19] Furst,M. L., Saxe, J. B., Sipser,M.: Parity, circuits and the polynomial-time hierarchy, Theory of Computing Systems (formerly Mathematical Systems Theory), 17(1), 1984, 13–27.
• [20] Gutiérrez-Escudero, R., Pérez-Jiménez, M. J., Rius-Font, M.: Characterizing tractability by tissue-like P systems, in: Workshop on Membrane Computing 10, vol. 5957 of Lecture Notes in Computer Science, Springer, 2009, 269–181.
• [21] Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., Riscos-Núñez, A., Romero-Campero, F. J.: Computational efficiency of dissolution rules in membrane systems, International Journal of Computer Mathematics, 83(7),2006, 593–611.
• [22] Head, T., Rozenberg, G., Bladergroen, R. S., Breek, C. K. D., Lommerse, P. H.M., Spaink, H. P.: Computing with DNA by operating on plasmids, Biosystems, 57(2), 2000, 87–93.
• [23] Hesse, W., Allender, E., Mix Barrington, D. A.: Uniform constant-depth threshold circuits for division and iterated multiplication, Journal of Computer and System Sciences, 65(4), 2002, 695–716.
• [24] Immerman, N.: Nondeterministic space is closed under complementation, SIAM Journal of Computing,17(5), 1988, 935–938.
• [25] Immerman, N.: Descriptive Complexity, Springer, 1999, ISBN 0387986006.
• [26] Ko, K.-I.: Distinguishing conjunctive and disjunctive reducibilities by sparse sets, Information and Computation,81(1), 1989, 62–87.
• [27] Ladner, R. E., Lynch, N. A., Selman, A. L.: A comparison of polynomial time reducibilities, Theoretical Computer Science, 1(2), 1975, 103–123.
• [28] Lipton, R. J.: DNA solution of hard computational problems, Science, 268(5210), 1995, 542–545.
• [29] Liu, Q., Wang, L., Frutos, A. G., Condon, A. E., Corn, R. M., Smith, L. M.: DNA computing on surfaces, Nature, 403(6766), 2000, 175–179.
• [30] Malchik, C., Winslow, A.: Tight Bounds for Active Self-Assembly Using an Insertion Primitive,ESA: The 22nd European Symposium on Algorithms, 2014, Accepted. Arxiv preprint:arXiv:1401.0359arXiv:1401.0359 [cs.FL].
• [31] Mauri, G., Leporati, A., Porreca, A. E., Zandron, C.: Recent complexity-theoretic results on P systems with active membranes, Journal of Logic and Computation, 2013, (awaiting publication).
• [32] Mix Barrington, D. A., Immerman, N., Straubing, H.: On uniformity within NC1, Journal of Computer and System Sciences, 41(3), 1990, 274–306.
• [33] Murphy, N.: Uniformity conditions for membrane systems: Uncovering complexity below P, Ph.D. Thesis, National University of Ireland Maynooth, 2010.
• [34] Murphy, N., Woods, D.: Active membrane systems without charges and using only symmetric elementary division characterise P, in: 8th International Workshop on Membrane Computing, vol. 4860 of Lecture Notes in Computer Science, Springer, 2007, 367–384.
• [35] Murphy, N., Woods, D.: A characterisation of NL using membrane systems without charges and dissolution, in: Unconventional Computing, 7th International Conference, UC 2008, Vienna, Austria, vol. 5204 of Lecture Notes in Computer Science, Springer, 2008, 164–176.
• [36] Murphy, N., Woods, D.: On acceptance conditions for membrane systems: characterisations of L and NL, Proceedings of the International Workshop on The Complexity of Simple Programs, 1, Electronic Proceedings in Theoretical Computer Science, 2009, Arxiv preprint: arXiv:0906.3327v1arXiv:0906.3327v1 [cs.CC].
• [37] Murphy, N., Woods, D.: The computational power of membrane systems under tight uniformity conditions,Natural Computing, 10(1), 2011, 613–632.
• [38] Murphy, N., Woods, D.: AND and/or OR: Uniform polynomial-size circuits, MCU: Proceedings of Machines,Computations and Universality, 128, Electronic Proceedings in Theoretical Computer Science, 2013,Arxiv preprint: arXiv:1212.3282v2arXiv:1212.3282v2 [cs.CC].
• [39] Ouyang, Q., Kaplan, P. D., Liu, S., Libchaber, A.: DNA solution of the Maximal Clique Problem, Science,278(5337), 1997, 446–449.
• [40] Pan, L., Pérez-Jiménez, M. J.: Computational complexity of tissue-like P systems, Journal of Complexity,26(3), 2010, 296–315.
• [41] Papadimitriou, C. H.: Computational Complexity, Addison Wesley, 1993, ISBN 0201530821.
• [42] Parberry, I.: Circuit complexity and neural networks, MIT Press, 1994, ISBN 0-262-16148-6.
• [43] Păun, G., Rozenberg, G., Salomaa, A., Eds.: The Oxford Handbook of Membrane Computing, Oxford University Press, Inc., New York, NY, USA, 2010, ISBN 0199556679, 9780199556670.
• [44] Pérez-Jiménez, M. J., Riscos-Núñez, A., Romero-Jiménez, A., Woods, D.: The Oxford Handbook of Membrane systems, chapter 12: Complexity – Membrane Division, Membrane Creation, Oxford University Press,2009, 302–336.
• [45] Pérez-Jiménez, M. J., Romero-Jiménez, A., Sancho-Caparrini, F.: Complexity classes in models of cellular computing with membranes, Natural Computing, 2(3), 2003, 265–285.
• [46] Porreca, A. E., Leporati, A., Mauri, G., Zandron, C.: Sublinear-space P systems with active membranes, in: Proceedings of the 13th International Conference on Membrane Computing 2012, vol. 7762 of Lecture Notesin Computer Science, Springer, 2013, 342–357.
• [47] Post, E. L.: Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, 50(5), 1944, 284–316.
• [48] Păun, G.: Membrane computing, in: Fundamentals of computation theory, vol. 2751 of Lecture Notes inComputer Science, Springer, 2003, 284–295.
• [49] Păun, G.: Further twenty six open problems in membrane computing, Proceedings of the Third Brainstorming Week on Membrane Computing, Fénix Editoria, 2005.
• [50] Qian, L., Winfree, E.: Scaling up digital circuit computation with DNA strand displacement cascades, Science,332(6034), 2011, 1196.
• [51] Rothemund, P. W., Winfree, E.: The program-size complexity of self-assembled squares, Proceedings of the thirty-second annual ACM symposium on Theory of computing, ACM, 2000.
• [52] Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks, Natural Computing, 7(4), 2008, 615–633.
• [53] Soloveichik, D., Winfree, E.: The computational power of Benenson automata, Theoretical Computer Science,344, 2005, 279–297.
• [54] Soloveichik, D., Winfree, E.: Complexity of self-assembled shapes, SIAM Journal of Computing, 36(6), 2007, 1544–1569.
• [55] Sosık, P.: The computational power of cell division in P systems: Beating down parallel computers?, Natural Computing, 2(3), 2003, 287–298.
• [56] Szelepcsényi, R.: The method of forced enumeration for nondeterministic automata, Acta Informatica, 26(3), 1988, 279–284.
• [57] Thachuk, C., Condon, A.: Space and energy efficient computation with DNA strand displacement systems, in: 18th International Conference on DNA Computing and Molecular Programming, vol. 7433 of Lecture Notes in Computer Science, Springer, 2012, 135–150.
• [58] Thachuk, C. J.: Space and energy efficient molecular programming and space efficient text indexing methods for sequence alignment, Ph.D. Thesis, University of British Columbia, 2013.
• [59] Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach, Springer-Verlag New York, Inc.,Secaucus, NJ, USA, 1999, ISBN 3540643109.
• [60] Woods, D., Chen, H.-L., Goodfriend, S., Dabby, N.,Winfree, E., Yin, P.: Active self-assembly of algorithmic shapes and patterns in polylogarithmic time, ITCS’13: Proceedings of the 4th conference on Innovations in Theoretical Computer Science, ACM, 2013, Full version: arXiv:1301.2626arXiv:1301.2626 [cs.DS].