Abstract
We propose a computational device based on evolutionary rules and communication within a network, similar to that introduced in [4], called network of evolutionary processors. An NP-complete problem is solved by networks of evolutionary processors of linear size in linear time. Some further directions of research are finally discussed.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. P. Banâtre, A. Coutant, D. Le Metayer, A parallel machine for multiset transformation and its programming style, Future Generation Computer Systems, 4 (1988), 133–144.
R. Constable, H. Hunt, S. Sahni, On the computational complexity of scheme equivalence, Technical Report No. 74-201, Dept. of Computer Science, Cornell University, Ithaca, NY, 1974.
E. Csuhaj-Varju, J. Dassow, J. Kelemen, Gh. Paun-Grammar Systems, Gordon and Breach, 1993.
E. Csuhaj-Varjú, Networks of parallel language processors. In New Trends in Formal Languages (Gh. Păun, A. Salomaa, eds.), LNCS 1218, Springer Verlag, 1997, 299–318
L. Errico, C. Jesshope, Towards a new architecture for symbolic processing. In Artificial Intelligence and Information-Control Systems of Robots’ 94 (I. Plander, ed.), World Sci. Publ., Singapore, 1994, 31–40.
S. E. Fahlman, G. E. Hinton, T. J. Seijnowski, Massively parallel architectures for AI: NETL, THISTLE and Boltzmann machines. In Proc. AAAI National Conf. on AI, William Kaufman, Los Altos, 1983, 109–113.
M. Garey, D. Johnson, Computers and Intractability. A Guide to the Theory of NP-completeness, Freeman, San Francisco, CA, 1979.
W. D. Hillis, The Connection Machine, MIT Press, Cambridge, 1985.
J. Hopcroft, J. Ulmann, Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, MA, 1969.
L. Kari, G. Gloor, S. Yu, Using DNA to solve the Bounded Correspondence Problem, Theoret. Comput. Sci., 231 (2000), 193–203.
Gh. Păun, Computing with membranes, J. Comput. Syst. Sci. 61(2000). (see also TUCS Research Report No. 208, November 1998, http://www.tucs.fi.)
Gh. Păun, G. Rozenberg, A. Salomaa, DNA Computing. New Computing Paradigms, Springer-Verlag, Berlin, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Castellanos, J., Martín-Vide, C., Mitrana, V., Sempere, J.M. (2001). Solving NP-Complete Problems with Networks of Evolutionary Processors. In: Mira, J., Prieto, A. (eds) Connectionist Models of Neurons, Learning Processes, and Artificial Intelligence. IWANN 2001. Lecture Notes in Computer Science, vol 2084. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45720-8_74
Download citation
DOI: https://doi.org/10.1007/3-540-45720-8_74
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42235-8
Online ISBN: 978-3-540-45720-6
eBook Packages: Springer Book Archive