×

On topological questions of real complexity theory and combinatorial optimization. (English) Zbl 0744.68058

Global Analysis - studies and applications IV, Lect. Notes Math 1453, 263-270 (1990).
[For the entire collection see Zbl 0708.00012.]
[This article is no translation of an article by the same author in Nov. Global’nom Anal. 1989, 58-74 (1989) as indicated in the contents.]
We continue the line started in A. M. Vershik [Topology and geometry, Lect. Notes Math. 1346, 557-581 (1981; Zbl 0649.52001)]; A. I. Barvinok, A. M. Vershik [Tr. Leningr. Mat. Obshchestra 1, 8- 26 (1991)]; A. I. Barvinok, A. M. Vershik [Funkts. Anal. Prilozh. 22(3), 66-67 (1988; Zbl 0688.20006)] and formulate a number of problems of the real complexity theory and combinatorial optimization as the problems investigating the properties of sequences of semialgebraic sets, their singularities, boundaries etc. The main idea is to apply the methods of real analysis and singularity theory to the study of spaces of problems and to treat the main notions of complexity theory ( \(P\), \(NP\), \(NP\)-completeness and others) as the complexity of different spectra of semialgebraic sets. The term “ configurational topology” is introduced in connection with the study of the topology of configuration spaces and Mnëv’s theorem on universality of configurations spaces or the spaces of convex polyhedrons from a topological point of view.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite