MASSIVE PARALLEL NETWORKS OF EVOLUTIONARY PROCESSORS AS NP-PROBLEM SOLVERS

Nuria Gómez Blas, Luis F. de Mingo, Eugenio Santos

2008

Abstract

This paper presents a new connectionist model that might be used to solve NP-problems. Most well known numeric models are Neural Networks that are able to approximate any function or classify any pattern set provided numeric information is injected into the net. Concerning symbolic information new research area has been developed, inspired by George Paun, called Membrane Systems. A step forward, in a similar Neural Network architecture, was done to obtain Networks of Evolutionary Processors (NEP). A NEP is a set of processors connected by a graph, each processor only deals with symbolic information using rules. In short, objects in processors can evolve and pass through processors until a stable configuration is reach. Despite their simplicity, we show how the latter networks might be used for solving an NP-complete problem, namely the 3-colorability problem, in linear time and linear resources (nodes, symbols, rules).

Paper Citation

in Harvard Style

Gómez Blas N., F. de Mingo L. and Santos E. (2008). MASSIVE PARALLEL NETWORKS OF EVOLUTIONARY PROCESSORS AS NP-PROBLEM SOLVERS . In Proceedings of the Tenth International Conference on Enterprise Information Systems - Volume 2: ICEIS, ISBN 978-989-8111-37-1, pages 588-592. DOI: 10.5220/0001721405880592

in Bibtex Style

@conference{iceis08,
author={Nuria Gómez Blas and Luis F. de Mingo and Eugenio Santos},
title={MASSIVE PARALLEL NETWORKS OF EVOLUTIONARY PROCESSORS AS NP-PROBLEM SOLVERS},
booktitle={Proceedings of the Tenth International Conference on Enterprise Information Systems - Volume 2: ICEIS,},
year={2008},
pages={588-592},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001721405880592},
isbn={978-989-8111-37-1},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Tenth International Conference on Enterprise Information Systems - Volume 2: ICEIS,
TI - MASSIVE PARALLEL NETWORKS OF EVOLUTIONARY PROCESSORS AS NP-PROBLEM SOLVERS
SN - 978-989-8111-37-1
AU - Gómez Blas N.
AU - F. de Mingo L.
AU - Santos E.
PY - 2008
SP - 588
EP - 592
DO - 10.5220/0001721405880592