All NP-problems can be solved in polynomial time by accepting hybrid networks of evolutionary processors of constant size

DOI10.1016/j.ipl.2007.03.001zbMath1184.68252MaRDI QIDQ2379954

Florin Manea, Victor Mitrana

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.03.001

zbMATH Keywords

Turing machine; formal languages; theory of computation; evolutionary processor; NP-language

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Universality of SNQ P Systems Using One Type of Spikes and Restrictive Rule Application, The role of evolutionary operations in accepting hybrid networks of evolutionary processors, Accepting networks of genetic processors are computationally complete, Small universal accepting hybrid networks of evolutionary processors, On small, reduced, and fast universal accepting networks of splicing processors, Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors, Simulating polarization by random context filters in networks of evolutionary processors, On the size of computationally complete hybrid networks of evolutionary processors, ON THE DESCRIPTIONAL COMPLEXITY OF ACCEPTING NETWORKS OF EVOLUTIONARY PROCESSORS WITH FILTERED CONNECTIONS, On Accepting Networks of Evolutionary Processors with at Most Two Types of Nodes, Accepting Networks of Non-inserting Evolutionary Processors

Cites Work

• Unnamed Item
• Accepting networks of splicing processors: complexity results
• Hybrid networks of evolutionary processors are computationally complete
• DNA Computing
• Machines, Computations, and Universality
• On the size complexity of universal accepting hybrid networks of evolutionary processors
• Aspects of Molecular Computing
• Introduction to evolutionary computing