Geodesic
In some curved spaces, one can solve NP-hard problems in polynomial time
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 224-250 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

In the late 1970s and the early 1980s, Yuri Matiyasevich actively used his knowledge of engineering and physical phenomena to come up with parallelized schemes for solving NP-hard problems in polynomial time. In this paper, we describe one such scheme in which we use parallel computation in curved spaces. Bibl. – 50 titles. 
@article{ZNSL_2008_358_a11,
     author = {V. Kreinovich and M. Margenstern},
     title = {In some curved spaces, one can solve {NP-hard} problems in polynomial time},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {224--250},
     year = {2008},
     volume = {358},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a11/}
}
TY  - JOUR
AU  - V. Kreinovich
AU  - M. Margenstern
TI  - In some curved spaces, one can solve NP-hard problems in polynomial time
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2008
SP  - 224
EP  - 250
VL  - 358
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a11/
LA  - en
ID  - ZNSL_2008_358_a11
ER  - 
%0 Journal Article
%A V. Kreinovich
%A M. Margenstern
%T In some curved spaces, one can solve NP-hard problems in polynomial time
%J Zapiski Nauchnykh Seminarov POMI
%D 2008
%P 224-250
%V 358
%U http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a11/
%G en
%F ZNSL_2008_358_a11
V. Kreinovich; M. Margenstern. In some curved spaces, one can solve NP-hard problems in polynomial time. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 224-250. http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a11/

[1] L. M. Adleman, “Molecular computation of solutions to combinatorial problems”, Science, 266:11 (1994), 1021–1024 | DOI

[2] M. Amos, Theoretical and Experimental DNA Computation, Springer-Verlag, Berlin, 2005 | MR

[3] M. Arbib, “Simple self-reproducing universal automata”, Inf. Control, 9 (1966), 177–189 | DOI | MR | Zbl

[4] M. A. Arbib, Theories of Abstract Automata, Prentice-Hall, Englewood Cliffs, NJ, 1969 | MR | Zbl

[5] M. A. Arbib, “The likelihood of the evolution of communicating intelligences on other planets”, Interstellar Communication: Scientific Perspectives, eds. C. Ponnamperuma, A. G. W. Cameron, Houghton Mifflin Co., Boston, MA, 1974, 63–66

[6] A. Blass, Yu. Gurevich, “Algorithms: a quest for absolute definitions”, Bull. Europ. Assoc. Theor. Comput. Sci., 81 (2003), 195–225 | MR | Zbl

[7] R. Bonola, Non-Euclidean Geometry, Dover Publications, Inc., New York, 1955 | MR | Zbl

[8] E. Börger, R. Stärk, Abstract State Machines: A Method for High-Level System Design and Analysis, Springer-Verlag, Berlin–Heidelberg–New York, 2003 | MR

[9] C. Boyce, Extraterrestrial Encounter: A Personal Perspective, David Charles, Newton Abbot–London, 1979

[10] K. Chelghoum, M. Margenstern, B. Martin, I. Pecci, “Cellular automata in the hyperbolic plane: proposal for a new environment”, Cellular Automata, Proceedings of the 6th International Conference on Cellular Automata for Research and Industry ACRI' 2004 (Amsterdam, October 25–28, 2004), Springer Lect. Notes Comput. Science, 3305, eds. P. M. A. Sloot, B. Chopard, A. G. Hoekstra, 2004, 678–687 | Zbl

[11] S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithms, McGraw-Hill, Boston, MA, 2006

[12] Y. Feldman, E. Shapiro, “Spatial machines: a more realistic approach to parallel computations”, Comm. ACM, 35:10 (1992), 61–73 | DOI

[13] R. A. Freitas, Jr., “A self-reproducing interstellar probe”, J. British Interplanet. Soc., 33 (1980), 251–264

[14] M. R. Garey, D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W. F. Freeman and Co., San Francisco, 1979 | MR | Zbl

[15] S. Grigorieff, M. Margenstern, “Register cellular automata in the hyperbolic plane”, Fund. Inform., 61:1 (2004), 19–27 | MR | Zbl

[16] D. Grigoriev, “Kolmogorov algorithms are stronger than Turing machines”, Zap. Nauchn. Semin. LOMI, 60, 1976, 29–37 | MR | Zbl

[17] Yu. Gurevich, “On Kolmogorov machines and related issues”, Bull. Europ. Assoc. Theor. Comput. Sci., 35 (1988), 71–82

[18] Yu. Gurevich, “Evolving algebras: an attempt to discover semantics”, Bull. Europ. Assoc. Theor. Comput. Sci., 43 (1991), 264–284 | Zbl

[19] Yu. Gurevich, “Evolving algebras: an attempt to discover semantics”, Current Trends in Theoretical Computer Science, eds. G. Rozenberg, A. Salomaa, World Scientific, Singapore, 1993, 266–292 | MR

[20] Yu. Gurevich, “Evolving algebras 1993: lipari guide”, Specification and Validation Methods, ed. E. Borger, Oxford University Press, Oxford, UK, 1995, 9–36 | MR | Zbl

[21] Yu. Gurevich, “Sequential abstract-state machines capture sequential algorithms”, ACM Transact. Computat. Logic (TOCL), 1:1 (2000), 77–111 | DOI | MR

[22] F. Herrmann, M. Margenstern, “A universal cellular automaton in the hyperbolic plane”, Theor. Comput. Sci., 296:2 (2003), 327–364 | DOI | MR | Zbl

[23] A. N. Kolmogorov, “On the concept of algorithm”, Usp. Mat. Nauk, 8:4 (1953), 175–176 | MR | Zbl

[24] A. N. Kolmogorov, V. A. Uspensky, “On the definition of algorithm”, Uspekhi Mat. Nauk, 13:4 (1958), 3–28 | MR | Zbl

[25] V. Kreinovich, G. Mints (eds.), Problems of Reducing the Exhaustive Search, Amer. Math. Soc., Providence, RI, 1997 | MR | Zbl

[26] L. A. Levin, “Universal search problems”, Problemy Peredachi Informatsii, 9:3 (1973), 115–116 | MR | Zbl

[27] H. R. Lewis, C. H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1997 | Zbl

[28] M. Margenstern, “New tools for cellular automata in the hyperbolic plane”, J. Universal Comput. Sci., 6:12 (2000), 1226–1252 | MR | Zbl

[29] M. Margenstern, “A combinatorial approach to hyperbolic geometry as a new perspective for computer science and technology”, Proceedings of the 18th International Conference on Computers and Their Applications ISCA' 03 (Honolulu, Hawaii, USA, March 26–28, 2003), ed. N. C. Debnath, 468–471

[30] M. Margenstern, “Cellular automata and combinatoric tilings in hyperbolic spaces. A survey”, Proceeding of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science DMTCS' 03 (Dijon, France, July 7–12, 2003), Springer Lect. Notes Computer Science, 2731, eds. C. Calude, M. J. Dinneen, V. Vajnovszki, 2003, 48–72 | MR | Zbl

[31] M. Margenstern, “The tiling of the hyperbolic 4D space by the 120-cell is combinatoric”, J. Universal Comput. Sci., 10:9 (2004), 1212–1238 | MR

[32] M. Margenstern, “A new way to implement cellular automata on the penta- and heptagrids”, J. Cell. Autom., 1:1 (2006), 1–24 | MR | Zbl

[33] M. Margenstern, “An algorithm for building intrinsically universal automata in hyperbolic spaces”, Proceedings of the 2006 International Conference on Foundations of Computer Science (Las Vegas, Nevada, USA, June 26–29, 2006), 3–9

[34] M. Margenstern, Cellular Automata in Hyperbolic Spaces, Vol. 1, Old City Publishing, Philadelphia, PA, 2007 ; Vol. 2 (to appear) | MR | Zbl

[35] M. Margenstern, K. Morita, “A polynomial solution for 3-SAT in the space of cellular automata in the hyperbolic plane”, J. Univ. Comput. Sci., 5:9 (1999), 563–573 | MR | Zbl

[36] M. Margenstern, K. Morita, “NP problems are tractable in the space of cellular automata in the hyperbolic plane”, Theor. Comput. Sci., 259:1–2 (2001), 99–128 | DOI | MR | Zbl

[37] M. Margenstern, G. Skordev, “Tools for devising cellular automata in the hyperbolic 3D space”, Fund. Inf., 58 (2003), 369–398 | MR | Zbl

[38] S. Yu. Maslov, Theory of Deductive Systems and Its Applications, MIT Press, Cambridge, MA, 1987 | MR | Zbl

[39] Yu. Matiyasevich, “Possible nontraditional methods of establishing unsatisfiability of propositional formulas”, Problems of reducing the exhaustive search, Amer. Math. Soc. Transl. Ser. 2, 178, eds. V. Kreinovich, G. Mints, Amer. Math. Soc., Providence, RI, 1997, 75–77 | MR

[40] D. Morgenstein, V. Kreinovich, “Which algorithms are feasible and which are not depends on the geometry of space-time”, Geombinatorics, 4:3 (1995), 80–97 | Zbl

[41] C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994 | MR | Zbl

[42] W. Reisig, “On Gurevich's theorem on sequential algorithms”, Acta Inf., 39:5 (2003), 273–305 | DOI | MR | Zbl

[43] R. Torres, G. R. Keller, V. Kreinovich, L. Longpré, S. A. Starks, “Eliminating duplicates under interval and fuzzy uncertainty: an asymptotically optimal algorithm and its geospatial applications”, Reliable Comput., 10:5 (2004), 401–422 | DOI | MR | Zbl

[44] B. A. Trakhtenbrot, “A survey of Russian approaches to perebor (Brute-force search) algorithms”, Ann. History Comput., 6:4 (1984), 384–400 | DOI | MR | Zbl

[45] V. A. Uspensky, A. L. Semenov, Algorithms: Main Ideas and Applications, Kluwer, Dordrecht, 1993

[46] F. Valdes, R. A. Freitas, “Comparison of reproducing and nonreproducing starprobe strategies for galactic exploration”, J. British Interplan. Soc., 33 (1980), 402–408

[47] J. von Neumann, A. W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press, Urbana, IL, 1966

[48] J. von Neumann, “Theory of self-reproducing automata”, Essays on Cellular Automata, ed. A. W. Burks, University of Illinois, Urbana, IL, 1969, 4–65

[49] G. von Tiesenhausen, W. A. Darbro, Self-Replicating Systems, NASA Technical Memorandum 78304, National Aeronautics and Space Administration (NASA), Washington, DC, 1980

[50] V. Zykov, E. Mytilinaios, B. Adams, H. Lipson, “Self-reproducing machines”, Nature, 435:7038 (2005), 163–164 | DOI