Abstract:
There are many unsolved problems in discrete mathematics and mathematical cybernetics. Writing a comprehensive survey of such problems involves great difficulties. First, such problems are rather numerous and varied. Second, they greatly differ from each other in degree of completeness of their solution. Therefore, even a comprehensive survey should not attempt to cover the whole variety of such problems; only the most important and significant problems should be reviewed. An impersonal choice of problems to include is quite hard. This paper includes 13 unsolved problems related to combinatorial mathematics and computational complexity theory. The problems selected give an indication of the author's studies for 50 years; for this reason, the choice of the problems reviewed here is, to some extent, subjective. At the same time, these problems are very difficult and quite important for discrete mathematics and mathematical cybernetics.
Bibliography: 74 items.
Keywords:graph reconstruction by subgraphs, Hamiltonian cycles, disjunctive normal forms, the snake-in-the-box problem, graph isomorphism, lower bounds, $\mathrm{NP}$-completeness, polynomial problems, Boolean functions hard to compute, cube piercing, perfect binary codes, Steiner triple systems.
Fulltext:
PDF file (610 kB)
