All NP-Problems Can Be Solved in Polynomial Time by Accepting Networks of Splicing Processors of Constant Size | SpringerLink
Skip to main content
Springer Nature Link
Log in

All NP-Problems Can Be Solved in Polynomial Time by Accepting Networks of Splicing Processors of Constant Size

  • Conference paper
DNA Computing (DNA 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4287))

Included in the following conference series:

Abstract

In this paper, we present two new results regarding ANSPs. The first one states that every recursively enumerable language can be accepted by an ANSP of size 7 out of which 6 do not depend on the given language. Then we propose a method for constructing, given an NP-language, an ANSP of size 7 accepting that language in polynomial time. Unlike the previous case, all nodes of this ANSP depend on the given language. Since each ANSP may be viewed as a problem solver as shown in [6], the later result may be interpreted as a method for solving every NP-problem in polynomial time by an ANSP of size 7.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Csuhaj-Varjú, E., Kari, L., Păun, G.: Test tube distributed systems based on splicing. Computers and AI 15, 211–232 (1996)

    MATH  Google Scholar 

  2. Errico, L., Jesshope, C.: Towards a new architecture for symbolic processing. In: Artificial Intelligence and Information-Control Systems of Robots 1994, pp. 31–40. World Scientific Publishing, Singapore (1994)

    Google Scholar 

  3. Fahlman, S.E., Hinton, G.E., Seijnowski, T.J.: Massively parallel architectures for AI: NETL, THISTLE and Boltzmann machines. In: Proc. AAAI National Conf. on AI, pp. 109–113. William Kaufman, Los Altos (1983)

    Google Scholar 

  4. Garey, M., Johnson, D.: Computers and Intractability. A Guide to the Theory of NP-completeness. Freeman, New York (1979)

    MATH  Google Scholar 

  5. Hillis, W.D.: The Connection Machine. MIT Press, Cambridge (1985)

    Google Scholar 

  6. Manea, F., Martín-Vide, C., Mitrana, V.: Accepting networks of splicing processors: complexity results. Theoretical Computer Science (to appear)

    Google Scholar 

  7. Martín-Vide, C., Mitrana, V.: Networks of evolutionary processors: results and perspectives. In: Molecular Computational Models: Unconventional Approaches, pp. 78–114. Idea Group Publishing, Hershey (2005)

    Google Scholar 

  8. Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing. New Computing Paradigms. Springer, Berlin (1998)

    MATH  Google Scholar 

  9. Păun, G.: Distributed architectures in DNA computing based on splicing: Limiting the size of components. In: Unconventional Models of Computation, pp. 323–335. Springer, Berlin (1998)

    Google Scholar 

  10. Sankoff, D., et al.: Gene order comparisons for phylogenetic inference:Evolution of the mitochondrial genome. Proc. Natl. Acad. Sci. USA 89, 6575–6579 (1992)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Mathematics and Computer Science, University of Bucharest, Str. Academiei 14, 70109, Bucharest, Romania

    Florin Manea & Victor Mitrana

  2. Research Group in Mathematical Linguistics, Rovira i Virgili University, Pça. Imperial Tarraco 1, 43005, Tarragona, Spain

    Carlos Martín-Vide & Victor Mitrana

Authors
  1. Florin Manea
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carlos Martín-Vide
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Victor Mitrana
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Chemistry, Purdue University, 560 Oval Drive, 47907-2084, West Lafayette, IN, USA

    Chengde Mao

  2. Faculty of Education and Integrated Arts and Sciences, Department of Mathematics, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, 169-8050, Tokyo, Japan

    Takashi Yokomori

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Manea, F., Martín-Vide, C., Mitrana, V. (2006). All NP-Problems Can Be Solved in Polynomial Time by Accepting Networks of Splicing Processors of Constant Size. In: Mao, C., Yokomori, T. (eds) DNA Computing. DNA 2006. Lecture Notes in Computer Science, vol 4287. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11925903_4

Download citation

  • DOI: https://doi.org/10.1007/11925903_4

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-49024-1

  • Online ISBN: 978-3-540-68423-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics