Биокомпьютеры 1
Ключевые слова:
компьютер, геном, клеточный автомат, матроид, категория, NP-сложностьАннотация
В статье предложены следующие результаты:
1). Существует ДНК-РНК вычислительный механизм X такой, что для произвольной NP-полной проблемы p:
(i) p разрешима;
(ii) ∀ π ∈p разрешима в полиномиальное время.
2). Существует 2-ленточный клеточный автомат (2LCA) такой, что для произвольной NP#-полной проблемы q:
(iii) q разрешим в полиномиальное вычислительное время.
Библиографические ссылки
Gritsak V. V. (Gritsak–Groener V. V.). // Proc. Nat. Acad. Sci. Ukraine SSR, ser. A, N6(1990)68.
Groener W. (Gritsak–Groener V. V.). Fundamental of Mathematical Cybernetics. MIT PRESS, 2004.
Gritsak-Groener V.V., Gritsak-Groener J. Arts Combinatoria. — Charkiv, NTU “ChPI”, 2003.
Alberts B., Bray D., Lewis J., Raff M., Roberts K., Watson J.D. Molecular biology of the cell. — New York, Garland Publishing, Inc., 1989.
Gritsak V. V. (Gritsak–Groener V. V.). Algorithms of Mathematical Chemistry. Preprint IK87-21. — Kyjiv, 1987.
Gritsak V. V. (Gritsak–Groener V. V.). Mathematical Chemistry. — SVITOZIR, Kyjiv, 1993.
Gritsak V. V. (Gritsak–Groener V. V.). // Proc. Nat. Acad. Sci. Ukraine SSR, ser. A, N7(1990)72.
Gritsak V. V. (Gritsak–Groener V. V.). Pattern Recognition Algorithms of Information in Hereditarely Al-phabets Languages. Algprithms an software. 1984. — Kyjiv, 1985.
Gritsak V. V. (Gritsak–Groener V. V.). Combinatorial-Geometry Optimization Problems for Elementary Toposes,// Proceedings Republican Seminary “Discrete Optimisatin”.1985, IK AN Ukraine, Kyjiv, (1985) 31.
Gritsak V. V. (Gritsak–Groener V. V.). // Visnyk Schevtshenko National University, ser. phys.-math. science, N1(1993)5.
Valery V.Gritsak–Groener, Julia Gritsak–Groener, Hamid R. Arabnia, Superpower Computational Creation for Biological Computing, Proceedings of the 2005 International Conference on Scientific Computing, Las Vegas, Nevada, USA June 20-23, 2005, pp.184-190.
