[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Plasmids to Solve #3SAT

  • Chapter
Aspects of Molecular Computing

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2950))

  • 772 Accesses

Abstract

Tom Head, [1] has given a simple and elegant method of aqueous computing to solve 3SAT. The procedure makes use of Divide-Delete-Drop operations performed on plasmids. In [4], a different set of operations, Cut-Expand-Ligate, are used to solve several NP-Complete problems. In this paper, we combine the features in the two procedures and define Cut-Delete-Expand-Ligate which is powerful enough to solve #3SAT, which is a counting version of 3SAT known to be in IP. The solution obtained is advantageous to break the propositional logic based cryptosystem introduced by J. Kari [5].

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

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Head, T.: Circular Suggestions for DNA Computing. In: Carbone, A., Gromov, M., Prusinkeiwicz, P. (eds.) Pattern Formation in Biology, Vision and Dynamics, pp. 325–335. World Scientific, Singapore (2000)

    Chapter  Google Scholar 

  2. Head, T.: Splicing Systems, Aqueous Computing, and Beyond. In: Antoniou, I., Calude, C.S., Dinneen, M.J. (eds.) Unconventional Models of Computation, UMC 2000, pp. 68–84. Springer, Berlin (2001)

    Google Scholar 

  3. Head, T., Rozenberg, G., Bladergreen, R.S., Breek, C.K.D., Lommerse, P.H.M., Spaink, H.P.S.: Computing with DNA by Operating on Plasmids. BioSystems 57, 87–93 (2000)

    Article  Google Scholar 

  4. Head, T., Yamamura, M., Gal, S.: Aqueous Computing: Writing on Molecules. In: Proc. Congress on Evolutionary Computation 1999, pp. 1006–1010. IEEE Service Center, Piscataway (1999)

    Google Scholar 

  5. Kari, J.: A Cryptosystem based on Propositional Logic. In: Dassow, J., Kelemen, J. (eds.) IMYCS 1988. 5th International Meeting of Young Computer Scientists, vol. 381, pp. 210–219. Springer, Heidelberg (1989)

    Chapter  Google Scholar 

  6. Siromoney, R., Bireswar, D.: DNA Algorithm for Breaking a Propositional Logic Based Cryptosystem. Bulletin of the EATCS 79, 170–176 (2003)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Siromoney, R., Das, B. (2003). Plasmids to Solve #3SAT. In: Jonoska, N., Păun, G., Rozenberg, G. (eds) Aspects of Molecular Computing. Lecture Notes in Computer Science, vol 2950. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24635-0_28

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-24635-0_28

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-20781-8

  • Online ISBN: 978-3-540-24635-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics