Uspekhi Matematicheskikh Nauk
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Subscription
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Uspekhi Mat. Nauk:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Uspekhi Mat. Nauk, 2009, Volume 64, Issue 5(389), Pages 3–20 (Mi umn9322)  

This article is cited in 1 scientific paper (total in 1 paper)

Some unsolved problems in discrete mathematics and mathematical cybernetics

A. D. Korshunov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

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.

DOI: https://doi.org/10.4213/rm9322

Full text: PDF file (610 kB)
References: PDF file   HTML file

English version:
Russian Mathematical Surveys, 2009, 64:5, 787–803

Bibliographic databases:

UDC: 510.5+519.1+519.7
MSC: Primary 68Qxx; Secondary 05Axx, 05Cxx, 94Bxx
Received: 28.08.2009

Citation: A. D. Korshunov, “Some unsolved problems in discrete mathematics and mathematical cybernetics”, Uspekhi Mat. Nauk, 64:5(389) (2009), 3–20; Russian Math. Surveys, 64:5 (2009), 787–803

Citation in format AMSBIB
\Bibitem{Kor09}
\by A.~D.~Korshunov
\paper Some unsolved problems in discrete mathematics and mathematical cybernetics
\jour Uspekhi Mat. Nauk
\yr 2009
\vol 64
\issue 5(389)
\pages 3--20
\mathnet{http://mi.mathnet.ru/umn9322}
\crossref{https://doi.org/10.4213/rm9322}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2588683}
\zmath{https://zbmath.org/?q=an:1185.68346}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2009RuMaS..64..787K}
\elib{https://elibrary.ru/item.asp?id=20425316}
\transl
\jour Russian Math. Surveys
\yr 2009
\vol 64
\issue 5
\pages 787--803
\crossref{https://doi.org/10.1070/RM2009v064n05ABEH004640}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000276915500001}
\elib{https://elibrary.ru/item.asp?id=15303038}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77149122379}


Linking options:
  • http://mi.mathnet.ru/eng/umn9322
  • https://doi.org/10.4213/rm9322
  • http://mi.mathnet.ru/eng/umn/v64/i5/p3

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. A. Evdokimov, “Tsepnye kody i Snake-in-the-Box Problem”, Uchen. zap. Kazan. un-ta. Ser. Fiz.-matem. nauki, 156, no. 3, Izd-vo Kazanskogo un-ta, Kazan, 2014, 55–65  mathnet
  • Успехи математических наук Russian Mathematical Surveys
    Number of views:
    This page:2378
    Full text:552
    References:56
    First page:145

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021